QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#549063#5665. AA Country and King DreamoonskrghariapaRE 0ms3512kbC++202.6kb2024-09-06 01:54:362024-09-06 01:54:36

Judging History

你现在查看的是最新测评结果

  • [2024-09-06 01:54:36]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3512kb
  • [2024-09-06 01:54:36]
  • 提交

answer

#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
using ll = long long;

vector<int> ke;
vector<bool> vis;
vector<bool> gabolehmundur;
vector<int> par;

void solve(){
    int n, noldepan, nolbelakang, dump;
    cin>>n;
    queue<int> q;
    int cq = 0;
    noldepan = -1;
    nolbelakang = -1;
    
    ke.clear();
    ke.resize(2*n+5, 0);
    vis.clear();
    vis.resize(n+3, false);
    gabolehmundur.clear();
    gabolehmundur.resize(n+3, false);
    par.clear();
    par.resize(n+3, 500000);
    vis[1] = true;
    ke[0] = 1;
    ke[2*n-2] = 1;

    // isi sama nandain nol

    for(int i = 0; i < 2*n-1; i++){
        cin>>ke[i];
        ke[0] = 1;
        ke[2*n-2] = 1;
        if(ke[i] == 0){
            if(i == 0 || ke[i-1] != 0)
                noldepan = i;
        }
        if(i != 0 && ke[i] != 0 && ke[i-1] == 0){
            nolbelakang = i-1;
        }
    }

    // ngasi parent
    for(int i = 1; i < noldepan; i++){
        if(par[ke[i-1]] != ke[i]){
            par[ke[i]] = ke[i-1];
        }
    }
    for(int i = 2*n - 3; i > nolbelakang; i--){
        if(par[ke[i+1]] != ke[i]){
            par[ke[i]] = ke[i+1];
        }
    }

    // ngasi gaboleh mundur
    for(int i = nolbelakang+1; i < 2*n-1; i++){
        if(i != 0 && ke[i] == par[ke[i-1]]) gabolehmundur[ke[i-1]] = true;
    }
    gabolehmundur[1] = true;

    // liat yang kosong
    for(int i = 1; i < 2*n-2; i++){
        if(ke[i] != 0 && ke[i-1] == par[ke[i]])
            vis[ke[i]] = true;
    }
    for(int i = 2; i <= n; i++){
        if(!vis[i]){
            q.push(i);
            cq++;
        }
    }

    // ngisi nol
    for(int i = noldepan; i <= nolbelakang; i++){
        if(i<0) continue;
        if(i == 0 || i == 2*n-2){
            ke[i] = 1;
            continue;
        }
        if(gabolehmundur[ke[i-1]]){
            ke[i] = q.front();
            // cout<<q.front()<<endl;
            par[ke[i]] = ke[i -1];
            q.pop();
            cq--;
        }
        else{
            if(cq==0 || par[ke[i - 1]] < q.front()){
                ke[i] = par[ke[i - 1]];
                gabolehmundur[ke[i - 1]] = true;
            }
            else{
                ke[i] = q.front();
                q.pop();
                cq--;
            }
        }
    }

    for(int i = 0; i < 2*n-2; i++){
        cout<<ke[i]<<" ";
    }
    cout<<ke[2*n-2]<<endl;
}

int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3512kb

input:

9
5
1 2 3 2 0 2 1 5 1
5
1 2 3 0 0 2 1 5 1
5
1 2 0 0 0 2 1 5 1
5
1 2 0 0 0 0 1 5 1
5
1 0 0 0 0 0 1 5 1
5
1 0 0 0 0 0 0 5 1
5
1 0 0 0 0 0 0 0 1
5
1 0 0 0 0 0 0 0 0
5
0 0 0 0 0 0 0 0 0

output:

1 2 3 2 4 2 1 5 1
1 2 3 2 4 2 1 5 1
1 2 3 2 4 2 1 5 1
1 2 1 3 1 4 1 5 1
1 2 1 3 1 4 1 5 1
1 2 1 3 1 4 1 5 1
1 2 1 3 1 4 1 5 1
1 2 1 3 1 4 1 5 1
1 2 1 3 1 4 1 5 1

result:

ok 9 lines

Test #2:

score: -100
Runtime Error

input:

28668
2
0 2 1
2
0 0 1
2
0 0 0
2
1 0 1
2
1 0 0
2
1 2 0
3
0 2 1 3 1
3
0 0 1 3 1
3
0 0 0 3 1
3
0 0 0 0 1
3
0 0 0 0 0
3
1 0 1 3 1
3
1 0 0 3 1
3
1 0 0 0 1
3
1 0 0 0 0
3
1 2 0 3 1
3
1 2 0 0 1
3
1 2 0 0 0
3
1 2 1 0 1
3
1 2 1 0 0
3
1 2 1 3 0
3
0 2 3 2 1
3
0 0 3 2 1
3
0 0 0 2 1
3
1 0 3 2 1
3
1 0 0 2 1
3
1 2 ...

output:

1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1 3 1
1 2 1 3 1
1 2 1 3 1
1 2 1 3 1
1 2 1 3 1
1 2 1 3 1
1 2 1 3 1
1 2 1 3 1
1 2 1 3 1
1 2 1 3 1
1 2 1 3 1
1 2 1 3 1
1 2 1 3 1
1 2 1 3 1
1 2 1 3 1
1 2 3 2 1
1 2 3 2 1
1 2 3 2 1
1 2 3 2 1
1 2 3 2 1
1 2 3 2 1
1 2 3 2 1
1 2 3 2 1
1 2 3 2 1
1 3 1 2 1
1 3 1 2 1
1 3 ...

result: