QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#717670 | #1873. Array | juan_123 | AC ✓ | 324ms | 27292kb | C++14 | 2.2kb | 2024-11-06 18:38:47 | 2024-11-06 18:38:47 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
priority_queue<pair<int,int> ,vector<pair<int,int> >,greater<pair<int,int> > >q,del;
int a[500005],b[500005],pre[500005],to[500005];
int n;
int c[500005];
bool check(){
int tot = 0,cnt =0 ;
for(int i = 0;i<=n;i++)c[i] = 0;
for(int i = 1;i<=n;i++)if(!c[a[i]])++tot,c[a[i]] = 1;
for(int i =0;i<=n;i++)c[i] = 0;
int l = 0;
for(int i = 1;i<=n;i++){
// cout << " " << i << endl;
if(i!=1){if(--c[a[i-1]]==0)--cnt;}
while(l<min(b[i],n)){
// cout << " " << l << endl;
++l;++c[a[l]];
if(c[a[l]] == 1)++cnt;
// cout << " " << l << " " << b[i] << " " << cnt << endl;
if(l!=b[i] and cnt == tot)return 0;
}
// cout << i << endl;
if(cnt!=tot and b[i]!=n+1)return 0;
}
// cout << 111 << endl;
return 1;
}
void solve(){
while(q.size())q.pop();while(del.size())del.pop();
cin >> n;
for(int i = 1;i<=n;i++)pre[i] = 0,to[i] = 0;
for(int i = 1;i<=n;i++)cin >> b[i];
int mx =n;
for(int i = 1;i<=n;i++)if(b[i]!=n+1)mx = min(mx,b[i]-i+1);
// for(int i = 1;i<=n;i++)cout << b[i]-i+1 << endl;
//cout <<" " << mx << endl;
if(b[1] == n+1 or mx <= 0){cout << "-1" << '\n';return;}
if(mx == 1){
int ok = 1;
for(int i = 1;i<=n;i++)if(b[i]!=i)ok=0;
if(!ok){cout << "-1" << '\n';return;}
else {
for(int i = 1;i<=n;i++)cout << 1 << " ";cout << '\n';
}
return;
}
for(int i = 1;i<n;i++){
if(b[i]>b[i+1]){cout << "-1" << '\n';return;}
if(b[i+1]!=b[i]){
pre[b[i+1]] = i;
to[i] = b[i+1];
}
}
for(int i = 1;i<mx;i++)q.push({0,i});
for(int i = 1;i<=n;i++){
if(pre[i] or i == b[1]){
if(pre[i])a[i] = a[pre[i]];
else a[i] = mx;
}else{
if(q.empty()){
cout << -1 << '\n';return;
}
assert(q.size());
a[i] = q.top().second;q.pop();
}
if(!to[i])q.push({i,a[i]});
}
//for(int i = 1;i<=n;i++)cout << a[i] << " ";cout << endl;
if(!check()){cout << -1 << '\n';}
else{
// cout << 1111 << endl;
for(int i = 1;i<=n;i++)cout << a[i] << " ";
cout << '\n';
}
return;
}
signed main(){
// freopen("sing2.in","r",stdin);
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t;cin >> t;
while(t--)solve();
return 0;
}/*
1
7
1 2 3 4 5 6 7
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 11824kb
input:
3 4 3 3 5 5 7 4 6 6 7 8 8 8 5 2 3 4 4 6
output:
1 1 2 2 1 2 3 4 2 1 3 -1
result:
ok 233
Test #2:
score: 0
Accepted
time: 245ms
memory: 27292kb
input:
23198 7 1 2 3 4 5 6 7 7 1 2 3 4 5 6 8 7 1 2 3 4 5 7 7 7 1 2 3 4 5 7 8 7 1 2 3 4 5 8 8 7 1 2 3 4 6 6 7 7 1 2 3 4 6 6 8 7 1 2 3 4 6 7 7 7 1 2 3 4 6 7 8 7 1 2 3 4 6 8 8 7 1 2 3 4 7 7 7 7 1 2 3 4 7 7 8 7 1 2 3 4 7 8 8 7 1 2 3 4 8 8 8 7 1 2 3 5 5 6 7 7 1 2 3 5 5 6 8 7 1 2 3 5 5 7 7 7 1 2 3 5 5 7 8 7 1 2 ...
output:
1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 233
Test #3:
score: 0
Accepted
time: 206ms
memory: 11892kb
input:
2000 1000 964 987 987 989 992 999 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 233
Test #4:
score: 0
Accepted
time: 287ms
memory: 18124kb
input:
16 100000 44700 98571 99279 99995 99998 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 1...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 233
Test #5:
score: 0
Accepted
time: 266ms
memory: 13568kb
input:
1006 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 233
Test #6:
score: 0
Accepted
time: 324ms
memory: 16244kb
input:
106 20000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 233
Test #7:
score: 0
Accepted
time: 276ms
memory: 25292kb
input:
58796 10 1 2 3 4 5 6 7 8 9 10 10 1 2 3 4 5 6 7 8 9 11 10 1 2 3 4 5 6 7 8 10 10 10 1 2 3 4 5 6 7 8 10 11 10 1 2 3 4 5 6 7 8 11 11 10 1 2 3 4 5 6 7 9 9 10 10 1 2 3 4 5 6 7 9 9 11 10 1 2 3 4 5 6 7 9 10 10 10 1 2 3 4 5 6 7 9 10 11 10 1 2 3 4 5 6 7 9 11 11 10 1 2 3 4 5 6 7 10 10 10 10 1 2 3 4 5 6 7 10 10...
output:
1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 233