QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#178896#6108. Permutation ArrangementZhou_JKWA 1ms5676kbC++232.6kb2023-09-14 15:04:302023-09-14 15:04:31

Judging History

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

  • [2023-09-14 15:04:31]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5676kb
  • [2023-09-14 15:04:30]
  • 提交

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'