QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#732691 | #5665. AA Country and King Dreamoon | Ashbourne | RE | 1ms | 7716kb | C++23 | 1.5kb | 2024-11-10 15:34:33 | 2024-11-10 15:34:34 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int a[N], Ton[N], fa[N];
void solve(){
int n, l = 0, r = n;
cin >> n;
vector<int> vis(n + 100);
for(int i = 1; i <= n; ++ i) Ton[i] = 0, fa[i] = 0;
// vector<int> a(2 * n + 1);
a[0] = 1e14; a[2 * n] = 1e14;
for(int i = 1; i <= 2 * n - 1; ++ i) cin >> a[i];
for(int i = 1; i <= 2 * n - 1; ++ i){
vis[a[i]] = 1;
if(a[i - 1] && !a[i]) l = i;
if(!a[i] && a[i + 1]) r = i;
}
int lx, rx;
vis[n + 1] = 1;
for(int i = 1; i <= n; ++ i){
if(vis[i - 1] && !vis[i]) lx = i;
if(!vis[i] && vis[i + 1]) rx = i;
}
// cout << l << " " << r << endl;
for(int i = r + 1; i <= 2 * n - 1; ++ i) Ton[a[i]]++;
if(l == 1 && r == 2 * n - 1){
for(int i = 1; i <= 2 * n - 1; ++ i){
if(i % 2 == 1) a[i] = 1;
else a[i] = i / 2 + 1;
cout << a[i] << " ";
}
cout << endl;
return;
}
if(l == 1){
a[1] = a[n];
l++;
}
// cout << l << " " << r << endl;
fa[a[1]] = 1e14;
for(int i = 2; i <= l - 1; ++ i){
if(!fa[a[i]]) fa[a[i]] = a[i - 1];
}
// cout << fa[3] << endl;
for(int i = l; i <= r; ++ i){
int rd = fa[a[i - 1]];
// cout << rd << endl;
bool flag = 1;
if(!rd || Ton[a[i - 1]]) flag = 0;
// cout << flag << endl;
if(flag && (rd < lx || lx > rx)){
a[i] = rd;
}else{
a[i] = lx++;
fa[a[i]] = a[i - 1];
}
}
for(int i = 1; i <= 2 * n - 1; ++i ){
cout << a[i] << " ";
}
cout << endl;
}
signed main(){
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--) solve();
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7716kb
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:
2 2 1 0 2 1 1 2 1 1 2 1 1 2 1 1 2 0 1 2 1 3 1 1 2 1 3 1 0 2 3 3 1 0 2 3 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 0 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 0 3 2 3 2 1 3 0 3 2 1 0 3 4 2 1 1 0 3 2 1 1 3 1 2 1 1 2 3 2 1 1 2 3 0 1 1 2 3 0 3 1 2 3...