QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #455846 | #6301. Minimum Suffix | sunkuangzheng | WA | 2ms | 11856kb | C++23 | 1.4kb | 2024-06-26 21:34:59 | 2024-06-26 21:35:00 |
Judging History
answer
/**
* author: sunkuangzheng
* created: 26.06.2024 20:43:34
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
int T,n,s[N],a[N],al[N],ar[N],pre[N],vl[N];
void los(){
cin >> n;
for(int i = 1;i <= n;i ++) cin >> a[i];
int pos = n;
while(pos >= 1){
for(int i = a[pos];i <= pos;i ++) al[i] = a[pos],ar[i] = pos;
pos = a[pos] - 1;
}for(int i = 1;i <= n;i ++) if(a[i] < al[i]) return cout << "-1\n",void();
int i = 2,j = 1;
for(;i <= n;){
if(a[i] == al[i]) pre[i] = j,vl[i] = 1,j = a[i ++];
else if(j - a[j] == i - a[i]) pre[i] = j ++,vl[i ++] = 0;
else return cout << "-1\n",void();
}pre[1] = 1,vl[1] = 1;
for(int j = al[n];j >= 1;j = al[j - 1]){
int fg = 0;
for(int i = j;i <= ar[j];i ++){
s[i] = s[pre[i]] + vl[i]; int val = s[ar[j] + 1 + i - al[j]],nxtl = ar[j] + 1 + i - al[j];
if(ar[j] != n && (s[i] < val && !fg || s[i] <= val && nxtl != ar[nxtl] && i == ar[j] && !fg)){
fg = 1;
while(!vl[i]) i --;
s[i] = val + 1;
}else if(ar[j] != n && s[i] > val) fg = 1;
}
}for(int i = 1;i <= n;i ++) cout << s[i] << " ",s[i] = 0;
cout << "\n";
}int main(){
ios::sync_with_stdio(0),cin.tie(0);
for(cin >> T;T --;) los();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11856kb
input:
6 3 1 1 1 3 1 1 2 3 1 1 3 3 1 2 1 3 1 2 2 3 1 2 3
output:
1 2 2 -1 1 2 1 1 1 2 2 1 2 1 1 1
result:
ok 16 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 11852kb
input:
2 2 1 1 2 1 2
output:
1 2 1 1
result:
ok 4 number(s): "1 2 1 1"
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 11788kb
input:
24 4 1 1 1 1 4 1 1 1 2 4 1 1 1 3 4 1 1 1 4 4 1 1 2 1 4 1 1 2 2 4 1 1 2 3 4 1 1 2 4 4 1 1 3 1 4 1 1 3 2 4 1 1 3 3 4 1 1 3 4 4 1 2 1 1 4 1 2 1 2 4 1 2 1 3 4 1 2 1 4 4 1 2 2 1 4 1 2 2 2 4 1 2 2 3 4 1 2 2 4 4 1 2 3 1 4 1 2 3 2 4 1 2 3 3 4 1 2 3 4
output:
1 2 2 2 -1 -1 1 2 2 1 -1 -1 -1 -1 1 2 1 3 -1 1 2 1 2 1 2 1 1 1 1 2 2 -1 -1 1 1 2 1 -1 2 1 2 2 -1 2 1 2 1 1 1 1 2 2 1 1 2 3 2 1 2 1 1 1 1
result:
wrong answer 56th numbers differ - expected: '2', found: '3'