QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#455849#6301. Minimum SuffixsunkuangzhengWA 2ms11912kbC++231.4kb2024-06-26 21:41:472024-06-26 21:41:48

Judging History

你现在查看的是最新测评结果

  • [2024-06-26 21:41:48]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:11912kb
  • [2024-06-26 21:41:47]
  • 提交

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] ++;
            }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();
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 11792kb

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: 11912kb

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: 0
Accepted
time: 1ms
memory: 9828kb

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 
2 2 1 2 
1 1 1 1 

result:

ok 63 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 11852kb

input:

120
5
1 1 1 1 1
5
1 1 1 1 2
5
1 1 1 1 3
5
1 1 1 1 4
5
1 1 1 1 5
5
1 1 1 2 1
5
1 1 1 2 2
5
1 1 1 2 3
5
1 1 1 2 4
5
1 1 1 2 5
5
1 1 1 3 1
5
1 1 1 3 2
5
1 1 1 3 3
5
1 1 1 3 4
5
1 1 1 3 5
5
1 1 1 4 1
5
1 1 1 4 2
5
1 1 1 4 3
5
1 1 1 4 4
5
1 1 1 4 5
5
1 1 2 1 1
5
1 1 2 1 2
5
1 1 2 1 3
5
1 1 2 1 4
5
1 1 2 ...

output:

1 2 2 2 2 
-1
-1
-1
1 2 2 2 1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 2 2 1 3 
-1
-1
1 2 2 1 2 
1 2 2 1 1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 2 1 3 2 
-1
-1
-1
1 2 1 3 1 
-1
-1
-1
-1
-1
1 2 1 2 2 
-1
1 3 1 2 2 
-1
1 2 1 2 1 
-1
-1
1 2 1 1 2 
2 3 2 1 2 
1 2 1 1 1 
1 1 2 2 2 
-1
-1...

result:

ok 256 numbers

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 11776kb

input:

720
6
1 1 1 1 1 1
6
1 1 1 1 1 2
6
1 1 1 1 1 3
6
1 1 1 1 1 4
6
1 1 1 1 1 5
6
1 1 1 1 1 6
6
1 1 1 1 2 1
6
1 1 1 1 2 2
6
1 1 1 1 2 3
6
1 1 1 1 2 4
6
1 1 1 1 2 5
6
1 1 1 1 2 6
6
1 1 1 1 3 1
6
1 1 1 1 3 2
6
1 1 1 1 3 3
6
1 1 1 1 3 4
6
1 1 1 1 3 5
6
1 1 1 1 3 6
6
1 1 1 1 4 1
6
1 1 1 1 4 2
6
1 1 1 1 4 3
6
...

output:

1 2 2 2 2 2 
-1
-1
-1
-1
1 2 2 2 2 1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 2 2 2 1 3 
-1
-1
-1
1 2 2 2 1 2 
1 2 2 2 1 1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-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:

wrong answer 889th numbers differ - expected: '3', found: '2'