双向链表 40 分求助
查看原帖
双向链表 40 分求助
604622
achjuncool楼主2022/10/5 19:46
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, cur, lst, curlen, nodes, tot, taken;
struct node{
    ll st, len, prv, nxt = 2e5 + 4, type;
    bool ex = false;
} a[200005], t;
bool exs[200005];
int main(){
    scanf("%lld%lld", &n, &cur);
    lst = cur;
    curlen = 1;
    memset(exs, 1, sizeof exs);
    for(ll i = 2; i <= n + 1; i++){
        if(i != n + 1) scanf("%lld", &cur);
        else cur = a[i - 1].type == 1 ? 0 : 1;
        if(cur == lst) curlen++;
        else {
            t.type = lst;
            lst = cur;
            t.st = i - curlen;
            t.len = curlen;
            t.ex = true;
            curlen = 1;
            a[++nodes] = t;
            a[nodes - 1].nxt = nodes;
            a[nodes].prv = nodes - 1;
        }
    }
    // for(ll i = 1; i <= nodes; i++) cout << a[i].st << " " << a[i].len << " " << a[i].type << endl;
    tot = nodes;
    while(taken < n){
        ll pos;
        for(ll i = 1; i <= nodes; i++){
            if(a[i].len >= 1){
                pos = i;
                break;
            }
        }
        while(pos != 2e5 + 4 && a[pos].len >= 1){
            a[pos].len--;
            while(true){
                if(exs[a[pos].st]) break;
                a[pos].st++;
            }
            taken++;
            printf("%lld ", a[pos].st);
            exs[a[pos].st] = false;
            pos = a[pos].nxt;
        }
        printf("\n");
        for(ll i = 1; i <= tot; i++){
            if(a[i].len == 0 && a[i].ex){
                a[i].ex = false;
                a[a[i].nxt].ex = false;
                a[a[i].prv].len += a[a[i].nxt].len;
                a[a[i].prv].nxt = a[a[i].nxt].nxt;
                a[a[a[i].nxt].nxt].prv = a[i].prv;
                nodes--;
            }
        }
    }
    return 0;
}
2022/10/5 19:46
加载中...