QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#199854 | #7346. Frogs | SolitaryDream# | WA | 31ms | 26476kb | C++20 | 1.4kb | 2023-10-04 14:21:59 | 2023-10-04 14:22:00 |
Judging History
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