QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#199788#7346. FrogsSolitaryDream#WA 1ms9884kbC++201.2kb2023-10-04 14:03:062023-10-04 14:03:07

Judging History

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

  • [2023-10-04 14:03:07]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:9884kb
  • [2023-10-04 14:03:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+1e3+7;

int n,a[N];

vector<int> v[N];

int p[N];

int w[N];

void dfs(int l,int r,int d)
{
    int t=(d+1)*2;
    if(l>r)
        return;
    vector<int> s;
    s.push_back(l);
    auto it=upper_bound(v[t].begin(),v[t].end(),l);
    while(it<v[t].end()&&*it<r)
        s.push_back(*it),it++;
    s.push_back(r);
    for(int i=0;i<s.size();i++)
    {
        p[s[i]]=s[(i+1)%s.size()];
        if(i<s.size())
            dfs(s[i]+1,s[i+1]-1,d+1);
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=2;i<n;i++)
        if(a[i-1]==a[i])
            v[a[i]].push_back(i);
    dfs(1,n,0);
    for(int i=1;i<=n;i++)
    {
        int l=i,r=p[i];
        if(l>r)
            swap(l,r);
        w[l]++,w[r]--;
    }
    for(int i=1;i<=n;i++)
        w[i]+=w[i-1];
    bool ok=1;
    for(int i=1;i<n;i++)
        if(w[i]!=a[i])
            ok=0;
    for(int i=1;i<=n;i++)
        if(!p[i])
            ok=0;
    if(!ok)
        puts("No");
    else
    {
        puts("Yes");
        for(int i=1;i<=n;i++)
            printf("%d%c",p[i]," \n"[i==n]);
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 8528kb

input:

5
2 4 2 2

output:

Yes
4 3 2 5 1

result:

ok Correct answer.

Test #2:

score: 0
Accepted
time: 1ms
memory: 9012kb

input:

4
1 2 3

output:

No

result:

ok Correct answer.

Test #3:

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

input:

2
0

output:

No

result:

wrong answer Expected YES, found NO on the first line