QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#434530 | #4800. Oscar's Round Must Have a Constructive Problem | ship2077 | TL | 1026ms | 4036kb | C++14 | 831b | 2024-06-08 16:29:53 | 2024-06-08 16:29:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
mt19937 mt(time(NULL));
constexpr int M=1e5+5;
int n,cnt,num,p[M],per[M];
int read(){
int x=0;char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
return x;
}
int rnd(int l,int r){return mt()%(r-l+1)+l;}
void solve(){ n=read();num=0;
for (int i=1;i<=n;i++) p[i]=read();
for (int i=1;i<=n;i++) num+=p[i]==p[1];
if (num==n) return puts("NO"),void();
iota(per+1,per+n+1,1);
cnt=0;while (1){ bool flag=0;
for (int i=1;i<n;i++)
if (per[i]==p[i]) flag=1,
swap(per[i],per[rnd(i+1,n)]);
if (per[n]==p[n]) swap(per[n],per[rnd(1,n-1)]),flag=1;
cnt++; if (!flag) break;
} puts("YES");
for (int i=1;i<=n;i++) printf("%d%c",per[i]," \n"[i==n]);
}
int main(){int T=read();while (T--) solve();return 0;}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3908kb
input:
3 3 3 3 3 3 3 2 1 6 1 1 4 5 1 4
output:
NO YES 1 3 2 YES 2 4 3 1 5 6
result:
ok ok
Test #2:
score: 0
Accepted
time: 18ms
memory: 3908kb
input:
50069 1 1 2 1 1 2 1 2 2 2 1 2 2 2 3 1 1 1 3 1 1 2 3 1 1 3 3 1 2 1 3 1 2 2 3 1 2 3 3 1 3 1 3 1 3 2 3 1 3 3 3 2 1 1 3 2 1 2 3 2 1 3 3 2 2 1 3 2 2 2 3 2 2 3 3 2 3 1 3 2 3 2 3 2 3 3 3 3 1 1 3 3 1 2 3 3 1 3 3 3 2 1 3 3 2 2 3 3 2 3 3 3 3 1 3 3 3 2 3 3 3 3 4 1 1 1 1 4 1 1 1 2 4 1 1 1 3 4 1 1 1 4 4 1 1 2 1 ...
output:
NO NO YES 2 1 YES 1 2 NO NO YES 3 2 1 YES 3 2 1 YES 3 1 2 YES 2 1 3 YES 3 1 2 YES 2 1 3 YES 2 1 3 YES 3 1 2 YES 1 2 3 YES 1 2 3 YES 3 2 1 YES 1 3 2 NO YES 1 3 2 YES 1 2 3 YES 1 2 3 YES 3 2 1 YES 1 2 3 YES 1 2 3 YES 2 3 1 YES 1 3 2 YES 2 3 1 YES 1 3 2 YES 1 2 3 YES 1 2 3 NO NO YES 4 2 3 1 YES 2 3 4 1...
result:
ok ok
Test #3:
score: 0
Accepted
time: 3ms
memory: 3656kb
input:
100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok ok
Test #4:
score: 0
Accepted
time: 26ms
memory: 3916kb
input:
50000 10 3 3 3 3 3 6 3 3 3 3 10 4 5 5 5 5 5 5 5 5 5 10 8 8 8 8 8 8 8 1 8 8 10 6 6 6 6 6 6 6 6 6 2 10 4 4 4 5 4 4 4 4 4 4 10 4 5 4 4 4 10 10 4 5 10 10 8 10 10 6 4 8 4 7 10 4 10 8 8 8 8 8 8 8 8 8 8 10 4 4 4 9 10 10 10 10 4 1 10 4 4 4 4 4 1 4 4 4 4 10 5 5 5 5 6 6 5 6 5 6 10 10 10 10 10 10 10 10 10 10 1...
output:
YES 1 2 8 10 5 3 7 9 6 4 YES 5 2 3 10 4 9 6 7 8 1 YES 1 2 3 4 5 6 7 8 9 10 YES 1 2 3 4 5 8 7 9 10 6 YES 1 2 3 4 5 6 7 8 9 10 YES 1 2 3 9 5 6 7 8 10 4 YES 1 2 3 4 5 6 7 8 9 10 NO YES 1 2 3 4 5 6 7 8 9 10 YES 6 2 9 8 10 4 1 5 3 7 YES 1 2 3 4 5 7 6 8 9 10 NO NO YES 1 2 3 4 5 6 7 8 10 9 YES 1 2 4 3 5 6 ...
result:
ok ok
Test #5:
score: 0
Accepted
time: 30ms
memory: 3932kb
input:
5000 100 37 37 37 58 58 58 58 58 58 58 37 58 37 37 37 58 37 37 37 37 58 58 37 37 37 37 58 37 58 58 58 58 37 58 58 58 37 58 37 37 37 37 58 37 37 37 58 37 37 58 37 37 37 58 37 37 58 37 58 58 58 58 37 37 58 58 58 37 37 58 58 37 37 58 37 58 58 37 58 58 58 37 58 58 37 58 58 58 37 58 58 58 37 58 58 37 58 ...
output:
YES 1 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 49 38 39 40 41 42 43 44 45 46 47 48 65 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 37 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 YES ...
result:
ok ok
Test #6:
score: 0
Accepted
time: 50ms
memory: 3964kb
input:
500 1000 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452...
output:
NO NO NO YES 1 2 3 174 5 6 219 8 477 991 687 846 13 761 237 472 669 18 19 20 21 22 23 792 25 26 142 939 91 30 789 32 50 34 534 36 37 602 990 40 41 42 43 44 340 46 855 48 410 942 961 52 398 531 55 56 57 58 59 60 973 62 63 659 65 66 67 95 69 124 71 526 73 74 161 718 976 301 79 80 81 539 83 84 85 343 3...
result:
ok ok
Test #7:
score: 0
Accepted
time: 363ms
memory: 3952kb
input:
50 10000 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9...
output:
YES 1 2 3 4 4185 6 8721 8 9 10 3682 12 7992 14 15 585 17 2086 19 2846 5702 22 9573 2722 6997 26 1289 28 29 4201 31 32 33 1303 35 36 37 38 39 2962 6347 8527 9046 44 45 46 47 48 49 50 51 4739 53 54 55 5511 4440 58 59 60 61 62 5979 7771 65 66 67 68 69 70 71 72 3879 74 4148 76 77 78 79 1170 81 82 4616 8...
result:
ok ok
Test #8:
score: 0
Accepted
time: 1026ms
memory: 4036kb
input:
20 25000 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2...
output:
YES 1 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 16327 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 515 92 93 94 95 611 97 98 99 100...
result:
ok ok
Test #9:
score: -100
Time Limit Exceeded
input:
10 50000 32825 31708 22702 32825 22702 31708 32825 32825 9333 31708 32825 46864 22702 32825 31708 31708 22702 22702 31708 46864 9333 9333 1785 31708 22702 9333 1785 32825 31708 22702 46864 32825 9333 46864 9333 35050 31708 1785 46864 9333 32825 1785 22702 31708 22702 1785 46864 32825 1785 35050 9333...
output:
YES 1 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 ...