QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#178896 | #6108. Permutation Arrangement | Zhou_JK | WA | 1ms | 5676kb | C++23 | 2.6kb | 2023-09-14 15:04:30 | 2023-09-14 15:04:31 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<set>
#include<vector>
#include<numeric>
#include<algorithm>
using namespace std;
const int N=200005;
int n;
int a[N],p[N];
int suf[N];
int pos[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
set<int>s;
for(int i=n;i>=1;i--)
{
suf[i]=suf[i+1];
if(a[i]==-1) suf[i]++;
else p[i]=a[i],pos[a[i]]=i;
}
for(int i=1;i<=n;i++)
if(!pos[i]) s.insert(i);
for(int i=1;i<=n;i++)
if(a[i]==-1)
{
if(suf[i]<=4)
{
vector<int>b;
for(int j=i;j<=n;j++)
if(a[j]==-1) b.emplace_back(j);
vector<int>val;
for(int v:s)
val.emplace_back(v);
vector<int>res(b.size());
iota(res.begin(),res.end(),0);
bool flag=false;
do
{
// for(int i=0;i<(int)b.size();i++)
// cerr<<res[i]<<" ";cerr<<"\n";
for(int i=0;i<(int)b.size();i++)
p[b[i]]=val[res[i]];
bool ok=true;
for(int j:b)
{
if((j-1>=1&&abs(p[j-1]-p[j])==1)||(j+1<=n&&abs(p[j+1]-p[j])==1))
{
ok=false;
break;
}
}
if(ok)
{
flag=true;
break;
}
}
while(next_permutation(res.begin(),res.end()));
if(flag) break;
else
{
cout<<"-1";
return 0;
}
}
else
{
bool flag=false;
for(int v:s)
{
if(i-1>=1&&abs(p[i-1]-v)==1) continue;
if(i+1<=n&&abs(p[i+1]-v)==1) continue;
p[i]=v;
flag=true;
s.erase(s.lower_bound(v));
break;
}
if(!flag)
{
cout<<"-1";
return 0;
}
}
}
for(int i=1;i<=n;i++)
cout<<p[i]<<" ";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3764kb
input:
10 3 -1 10 -1 8 -1 -1 -1 -1 -1
output:
3 1 10 2 8 4 6 9 5 7
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 5676kb
input:
2 -1 -1
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 5648kb
input:
10 -1 -1 -1 8 -1 2 10 -1 -1 3
output:
4 6 1 8 5 2 10 7 9 3
result:
wrong answer 1st numbers differ - expected: '1', found: '4'