QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#624597 | #6108. Permutation Arrangement | lmy11 | WA | 0ms | 3832kb | C++23 | 1.6kb | 2024-10-09 16:12:49 | 2024-10-09 16:12:49 |
Judging History
answer
#include<bits/stdc++.h>
const int N=2e5+5;
using namespace std;
int read()
{
int f=1,x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
f=-f;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
void write(int x)
{
if(x<0)
{
x=-x;
putchar('-');
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
string reads()
{
string s;
char ch=getchar();
while(ch==' '||ch=='\n')
{
ch=getchar();
}
while(ch!=' '&&ch!='\n')
{
s+=ch;
ch=getchar();
}
return s;
}
void writes(string s)
{
for(int i=0;i<(int)s.length();i++)
{
putchar(s[i]);
}
}
priority_queue< int,vector<int>,greater<int> >q;
bool f[N];
int s[N];
int ans[N];
int n;
void dfs(int x)
{
if(x==n+1)
{
for(int i=1;i<=n;i++)
{
write(ans[i]);
putchar(' ');
}
puts("");
exit(0);
}
if(ans[x]!=-1) dfs(x+1);
int a[6];
for(int i=1;i<=min((int)q.size(),5);i++)
{
for(int j=1;j<=i;j++)
{
a[j]=q.top();
q.pop();
}
for(int j=1;j<i;j++) q.push(a[j]);
if(abs(ans[x-1]-a[i])>1 && abs(ans[x+1]-a[i])>1)
{
ans[x]=a[i];
dfs(x+1);
}
q.push(a[i]);
ans[x]=-1;
}
// if(q.size()>=5)
// {
// write(-1);
// puts("");
// exit (0);
// }
}
int main()
{
n=read();
ans[0]=-1;
ans[n+1]=-1;
for(int i=1;i<=n;i++)
{
s[i]=read();
if(s[i]!=-1) f[s[i]]=1;
ans[i]=s[i];
}
for(int i=1;i<=n;i++)
if(!f[i])
q.push(i);
// cout<<q.size()<<endl;
dfs(1);
write(-1);
puts("");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3548kb
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: 0ms
memory: 3800kb
input:
2 -1 -1
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
10 -1 -1 -1 8 -1 2 10 -1 -1 3
output:
1 4 6 8 5 2 10 7 9 3
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
10 -1 2 -1 6 -1 1 -1 5 -1 3
output:
4 2 8 6 9 1 7 5 10 3
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
10 -1 3 -1 -1 5 -1 9 -1 -1 -1
output:
1 3 6 2 5 7 9 4 8 10
result:
ok 10 numbers
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 3548kb
input:
10 4 -1 8 -1 -1 3 -1 9 -1 6
output:
-1
result:
wrong answer 1st numbers differ - expected: '4', found: '-1'