QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#549063 | #5665. AA Country and King Dreamoon | skrghariapa | RE | 0ms | 3512kb | C++20 | 2.6kb | 2024-09-06 01:54:36 | 2024-09-06 01:54:36 |
Judging History
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 ...