QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#199854#7346. FrogsSolitaryDream#WA 31ms26476kbC++201.4kb2023-10-04 14:21:592023-10-04 14:22:00

Judging History

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

  • [2023-10-04 14:22:00]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:26476kb
  • [2023-10-04 14:21:59]
  • 提交

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)
    {
        p[l]=l;
        return;
    }
    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]&&a[i])
            v[a[i]].push_back(i);
    for(int i=1,j;i<=n;i=j+1)
    {
        j=i;
        while(j<n&&a[j])
            j++;
        dfs(i,j,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: 2ms
memory: 10096kb

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: 8660kb

input:

4
1 2 3

output:

No

result:

ok Correct answer.

Test #3:

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

input:

2
0

output:

Yes
1 2

result:

ok Correct answer.

Test #4:

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

input:

2
2

output:

Yes
2 1

result:

ok Correct answer.

Test #5:

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

input:

2
1

output:

No

result:

ok Correct answer.

Test #6:

score: 0
Accepted
time: 0ms
memory: 9944kb

input:

3
0 0

output:

Yes
1 2 3

result:

ok Correct answer.

Test #7:

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

input:

3
2 0

output:

Yes
2 1 3

result:

ok Correct answer.

Test #8:

score: 0
Accepted
time: 0ms
memory: 8532kb

input:

3
0 2

output:

Yes
1 3 2

result:

ok Correct answer.

Test #9:

score: 0
Accepted
time: 0ms
memory: 10168kb

input:

3
2 2

output:

Yes
2 3 1

result:

ok Correct answer.

Test #10:

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

input:

3
2 4

output:

No

result:

ok Correct answer.

Test #11:

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

input:

3
1 0

output:

No

result:

ok Correct answer.

Test #12:

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

input:

3
1 1

output:

No

result:

ok Correct answer.

Test #13:

score: 0
Accepted
time: 22ms
memory: 11456kb

input:

200000
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...

output:

Yes
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 10...

result:

ok Correct answer.

Test #14:

score: 0
Accepted
time: 23ms
memory: 26448kb

input:

200000
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 170 172 17...

output:

Yes
200000 199999 199998 199997 199996 199995 199994 199993 199992 199991 199990 199989 199988 199987 199986 199985 199984 199983 199982 199981 199980 199979 199978 199977 199976 199975 199974 199973 199972 199971 199970 199969 199968 199967 199966 199965 199964 199963 199962 199961 199960 199959 19...

result:

ok Correct answer.

Test #15:

score: 0
Accepted
time: 31ms
memory: 26476kb

input:

199999
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 170 172 17...

output:

Yes
199999 199998 199997 199996 199995 199994 199993 199992 199991 199990 199989 199988 199987 199986 199985 199984 199983 199982 199981 199980 199979 199978 199977 199976 199975 199974 199973 199972 199971 199970 199969 199968 199967 199966 199965 199964 199963 199962 199961 199960 199959 199958 19...

result:

ok Correct answer.

Test #16:

score: 0
Accepted
time: 25ms
memory: 10788kb

input:

200000
2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2...

output:

Yes
2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19 22 21 24 23 26 25 28 27 30 29 32 31 34 33 36 35 38 37 40 39 42 41 44 43 46 45 48 47 50 49 52 51 54 53 56 55 58 57 60 59 62 61 64 63 66 65 68 67 70 69 72 71 74 73 76 75 78 77 80 79 82 81 84 83 86 85 88 87 90 89 92 91 94 93 96 95 98 97 100 99 102 ...

result:

ok Correct answer.

Test #17:

score: 0
Accepted
time: 2ms
memory: 9980kb

input:

14
2 4 2 2 2 4 6 6 6 4 4 2 0

output:

Yes
4 3 2 5 13 11 8 9 10 7 12 6 1 14

result:

ok Correct answer.

Test #18:

score: 0
Accepted
time: 2ms
memory: 8516kb

input:

7
2 4 4 4 2 0

output:

Yes
6 3 4 5 2 1 7

result:

ok Correct answer.

Test #19:

score: 0
Accepted
time: 0ms
memory: 9912kb

input:

3
0 0

output:

Yes
1 2 3

result:

ok Correct answer.

Test #20:

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

input:

7
0 2 2 2 2 0

output:

Yes
1 3 4 5 6 2 7

result:

ok Correct answer.

Test #21:

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

input:

20
0 2 4 6 8 6 8 6 6 4 4 4 2 2 4 6 4 2 0

output:

No

result:

wrong answer Expected YES, found NO on the first line