QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #120548 | #1873. Array | 1kri | RE | 0ms | 11832kb | C++14 | 1.9kb | 2023-07-06 21:10:46 | 2023-07-06 21:10:48 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <cassert>
using namespace std;
int read(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
int t,n,B[200005];
int l[200005],r[200005];
vector<pair<int,int>> ins[200005];
int p[200005];
int a[200005];
int cnt[200005];
int main(){
t=read();
while(t--){
n=read();
assert(n<=7);
for (int i=1;i<=n;i++)l[i]=0,r[i]=i-1;
int x=n+1;
for (int i=1;i<=n;i++){
B[i]=read();
if (B[i]<n)l[B[i]+1]=max(l[B[i]+1],i);
if (B[i]!=n+1)r[B[i]]=min(r[B[i]],i-1);
if (B[i]==n+1&&x==n+1)x=i;
}
for (int i=1;i<=n;i++)l[i]=max(l[i],l[i-1]);
set<int> c;
for (int i=1;i<=n;i++)
if (i!=x-1)c.insert(i);
int fg=1;
for (int i=1;i<=n;i++)ins[r[i]].push_back(make_pair(l[i],i));
for (int i=0;i<=n;i++){
for (int j=0;j<(int)ins[i].size();j++)
if (ins[i][j].first>0){
set<int>::iterator it=c.lower_bound(ins[i][j].first);
if (it!=c.end()&&(*it)<=i)p[ins[i][j].second]=(*it),c.erase(it);
else fg=0;
}
else p[ins[i][j].second]=0;
}
for (int i=0;i<=n;i++)
for (int j=0;j<(int)ins[i].size();j++)
if (ins[i][j].first==0){
if (c.begin()!=c.end()&&(*c.begin())<=i)p[ins[i][j].second]=(*c.begin()),c.erase(c.begin());
}
for (int i=0;i<=n;i++)ins[i].clear();
if (fg==1){
int tot=0;
for (int i=1;i<=n;i++)
if (p[i]==0)a[i]=++tot;
else a[i]=a[p[i]];
int qwq=0;
int j=n+1;
for (int i=n;i>=1;i--){
cnt[a[i]]++;
if (cnt[a[i]]==1){
qwq++;
if (qwq==tot)j=n;
}
while(qwq==tot&&j>i&&cnt[a[j]]>1){
cnt[a[j]]--;
j--;
}
if (j!=B[i])fg=0;
}
for (int i=1;i<=n;i++)cnt[a[i]]=0;
}
if (fg==0)printf("-1\n");
else{
for (int i=1;i<=n;i++)printf("%d ",a[i]);
printf("\n");
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 11832kb
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: -100
Dangerous Syscalls
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 ...