QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #84130 | #5665. AA Country and King Dreamoon | HOLIC# | WA | 43ms | 13736kb | C++20 | 3.7kb | 2023-03-05 18:10:11 | 2023-03-06 01:00:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 6e5 + 10;
int a[N], pos[N], fa[N], pas[N], n;
int b[N], g[N];
inline void work(int c, int d){
int st = c;
for(int i = c; i <= d; ++i) pos[a[i]] = 0;
int al = (d - c) / 2;
for(int i = c; i <= d; ++i){
if(a[i]){
if(pos[a[i]]) --al;
else pos[a[i]] = i, fa[a[i]] = a[i - 1];
}
}
int now = a[c], p = 2; fa[now] = 2e9;
for(int i = c; i <= d; ++i){
if(!a[i]){
while(p <= n && pas[p]) ++ p;
if(al){
if(fa[now] < p){
a[i] = now = fa[now], --al;
}else{
fa[p] = now, a[i] = now = p; ++p;
}
}else{
fa[p] = now, a[i] = now = p, ++p;
}
}else{
now = a[i];
}
}
}
int main(){
int T;
scanf("%d", &T);
while(T --){
scanf("%d", &n);
for(int i = 1; i <= n; ++i) pos[i] = fa[i] = pas[i] = 0;
int m = n + n - 1;
int al = n - 1;
for(int i = 1; i <= m; ++i){
scanf("%d", &a[i]);
if(i == 1 || i == m) a[i] = 1;
if(a[i]){
if(pos[a[i]]) -- al;
else pos[a[i]] = i, fa[a[i]] = a[i - 1];
pas[a[i]] = i;
}
}
int l = -1, r;
for(int i = 2; i < m; ++i){
if(!a[i]){
l = i;
for(int j = i; j < m; ++j){
if(!a[j]) r = j;
else break;
}
break;
}
}
if(l != -1){
if(pos[a[r + 1]] == r + 1){
for(int i = 1; i <= n; ++i) pos[i] = 0;
for(int i = r + 1; i <= m; ++i) pos[a[i]] = i;
for(int i = 1; i < l; ++i) if(pos[a[i]]) fa[a[i]] = 2e9;
for(int i = 1; i <= n; ++i) pos[i] = 0;
for(int i = 1; i < l; ++i) pos[a[i]] = i;
int cnt1 = 0, cnt2 = 0;
for(int i = r + 1; i <= m; ++i){
if(!pos[a[i]]){
if(i & 1) b[++cnt1] = a[i], pos[a[i]] = i;
else g[++cnt2] = a[i], pos[a[i]] = i;
}
}
sort(b + 1, b + cnt1 + 1), sort(g + 1, g + cnt2 + 1);
int now = a[l - 1], p = 2, L = 1, R = 1;
for(int i = l; i <= r; ++i){
while(p <= n && pas[p]) ++p;
if(al){
if(i & 1){
if(L <= cnt1 && b[L] < p && b[L] < fa[now]){
--al, fa[b[L]] = now, now = a[i] = b[L]; fa[b[L]] = 2e9, ++L;
}else{
if(fa[now] < p) now = a[i] = fa[now], --al;
else fa[p] = now, now = a[i] = p, ++p;
}
}else{
if(R <= cnt2 && g[R] < p && g[R] < fa[now]){
--al, fa[g[R]] = now, now = a[i] = g[R]; fa[g[R]] = 2e9, ++R;
}else{
if(fa[now] < p) now = a[i] = fa[now], --al;
else fa[p] = now, now = a[i] = p, ++p;
}
}
}else fa[p] = now, now = a[i] = p, ++p;
}
}else{
work(pos[a[r + 1]], r + 1);
}
}
for(int i = 1; i <= m; ++i) printf("%d ", a[i]);
puts("");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11696kb
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
Wrong Answer
time: 43ms
memory: 13736kb
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...
result:
wrong answer 246th lines differ - expected: '1 3 1 4 1 2 1', found: '1 2 3 4 1 2 1 '