| Task: | Polygonal Chain |
| Sender: | AMnu |
| Submission time: | 2021-01-30 03:38:56 +0200 |
| Language: | C++ (C++17) |
| Status: | READY |
| Result: | 22 |
| group | verdict | score |
|---|---|---|
| #1 | ACCEPTED | 7 |
| #2 | TIME LIMIT EXCEEDED | 0 |
| #3 | ACCEPTED | 15 |
| #4 | TIME LIMIT EXCEEDED | 0 |
| #5 | TIME LIMIT EXCEEDED | 0 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | ACCEPTED | 0.01 s | 1, 2, 4, 5 | details |
| #2 | ACCEPTED | 0.01 s | 1, 2, 4, 5 | details |
| #3 | ACCEPTED | 0.01 s | 1, 2, 4, 5 | details |
| #4 | ACCEPTED | 0.01 s | 1, 2, 4, 5 | details |
| #5 | ACCEPTED | 0.01 s | 1, 2, 4, 5 | details |
| #6 | TIME LIMIT EXCEEDED | -- | 2, 4, 5 | details |
| #7 | TIME LIMIT EXCEEDED | -- | 2, 4, 5 | details |
| #8 | TIME LIMIT EXCEEDED | -- | 2, 4, 5 | details |
| #9 | TIME LIMIT EXCEEDED | -- | 2, 4, 5 | details |
| #10 | TIME LIMIT EXCEEDED | -- | 2, 4, 5 | details |
| #11 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
| #12 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #13 | ACCEPTED | 0.01 s | 3, 4, 5 | details |
| #14 | ACCEPTED | 0.01 s | 3, 4, 5 | details |
| #15 | ACCEPTED | 0.01 s | 1, 2, 4, 5 | details |
| #16 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
| #17 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
| #18 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #19 | ACCEPTED | 0.01 s | 1, 2, 4, 5 | details |
| #20 | TIME LIMIT EXCEEDED | -- | 2, 4, 5 | details |
| #21 | TIME LIMIT EXCEEDED | -- | 2, 4, 5 | details |
| #22 | TIME LIMIT EXCEEDED | -- | 2, 4, 5 | details |
| #23 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
| #24 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
| #25 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
| #26 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #27 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #28 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #29 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #30 | ACCEPTED | 0.01 s | 1, 2, 4, 5 | details |
Code
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int N, pos;
long long A[MAXN];
int B[MAXN];
long long L[MAXN];
long long R[MAXN];
int H[MAXN];
long long LL, RR;
string S;
bool cek() {
for (int i=0;i<N;i++) {
B[H[i]]=i;
}
for (int i=0;i<N-1;i++) {
long long x, y, z;
if (S[i]=='U') {
x=B[i];
y=B[i+1];
}
else {
x=B[i+1];
y=B[i];
}
if (x>y) {
return 0;
}
if (i&1) {
z=L[i];
}
else {
z=R[i];
}
for (int j=x+1;j<y;j++) {
if (L[H[j]]<=z&&z<=R[H[j]]) {
return 0;
}
}
}
return 1;
}
bool brute(int x) {
if (x==N) {
return cek();
}
for (H[x]=0;H[x]<N;H[x]++) {
for (int i=0;1;i++) {
if (i==x) {
if (brute(x+1)) {
return 1;
}
}
if (H[i]==H[x]) {
break;
}
}
}
return 0;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>N;
for (int i=0;i<N;i++) {
cin>>A[i];
if (i&1) {
L[i]=R[i]-A[i];
L[i+1]=L[i];
}
else {
R[i]=L[i]+A[i];
R[i+1]=R[i];
}
LL=min(LL,L[i]);
RR=max(RR,R[i]);
}
cin>>S;
if (RR-LL<=2) {
for (int i=0;i<N-1;i++) {
if (pos==0) {
if (A[i]==1) {
if (i>0&&S[i]!=S[i-1]) {
cout<<"NO\n";
return 0;
}
B[i]=1;
}
else {
B[i]=MAXN;
pos=1;
}
}
else if (pos==1) {
if (A[i]==1) {
if (S[i]!=S[i-1]) {
cout<<"NO\n";
return 0;
}
B[i]=1;
}
else {
if (S[i]==S[i-1]) {
B[i]=1;
}
else {
B[i-1]=MAXN;
B[i]=1;
pos=2;
}
}
}
else {
if (A[i]==1) {
if (S[i]!=S[i-1]) {
cout<<"NO\n";
return 0;
}
B[i]=1;
}
else {
cout<<"NO\n";
return 0;
}
}
}
if (pos==2&&A[N-1]==2) {
cout<<"NO\n";
return 0;
}
cout<<"YES\n";
cout<<B[0];
for (int i=1;i<N-1;i++) {
cout<<' '<<B[i];
}
cout<<'\n';
return 0;
}
if (!brute(0)) {
cout<<"NO\n";
return 0;
}
for (int i=0;i<N;i++) {
B[H[i]]=i;
}
for (int i=0;i<N-1;i++) {
B[i]=abs(B[i]-B[i+1]);
}
cout<<"YES\n";
cout<<B[0];
for (int i=1;i<N-1;i++) {
cout<<' '<<B[i];
}
cout<<'\n';
}
Test details
Test 1
Group: 1, 2, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 2 2 10 D |
| correct output |
|---|
| YES 1 |
| user output |
|---|
| YES 1 |
Test 2
Group: 1, 2, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 8 5 8 7 5 6 5 3 4 DUUUDDD |
| correct output |
|---|
| YES 1 5 1 1 3 1 1 |
| user output |
|---|
| YES 1 5 1 1 3 1 1 |
Test 3
Group: 1, 2, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 8 9 8 8 10 10 8 9 10 DDDUUUD |
| correct output |
|---|
| YES 1 1 1 4 1 1 7 |
| user output |
|---|
| YES 1 1 1 5 1 1 3 |
Test 4
Group: 1, 2, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 8 9 10 8 8 9 9 7 8 DDDDUUU |
| correct output |
|---|
| NO |
| user output |
|---|
| NO |
Test 5
Group: 1, 2, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 8 10 2 8 3 10 2 10 10 DDUUUUD |
| correct output |
|---|
| YES 1 1 3 1 1 1 7 |
| user output |
|---|
| YES 1 1 3 2 1 1 3 |
Test 6
Group: 2, 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 15 73 74 97 82 19 50 26 51 56 93 ... |
| correct output |
|---|
| YES 1 2 3 1 1 3 1 1 1 10 1 3 1 1 |
| user output |
|---|
| (empty) |
Test 7
Group: 2, 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 15 95 71 97 77 98 76 100 62 96 69... |
| correct output |
|---|
| YES 1 1 3 1 1 1 1 1 9 1 11 1 13 1 |
| user output |
|---|
| (empty) |
Test 8
Group: 2, 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 15 79 81 84 86 88 90 92 92 91 89 ... |
| correct output |
|---|
| YES 1 2 3 4 5 6 14 1 6 5 4 3 2 1 |
| user output |
|---|
| (empty) |
Test 9
Group: 2, 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 15 97 90 87 83 79 76 74 23 24 76 ... |
| correct output |
|---|
| YES 13 11 9 7 5 3 1 1 3 5 7 9 11 1... |
| user output |
|---|
| (empty) |
Test 10
Group: 2, 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 15 100 2 99 1 78 4 93 2 100 1 15 ... |
| correct output |
|---|
| NO |
| user output |
|---|
| (empty) |
Test 11
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 1000 999997 999995 999993 999991 99... |
| correct output |
|---|
| YES 997 995 993 991 989 987 985 98... |
| user output |
|---|
| (empty) |
Test 12
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 999999998 999999996 999999994 ... |
| correct output |
|---|
| YES 99997 99995 99993 99991 99989 ... |
| user output |
|---|
| (empty) |
Test 13
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
| correct output |
|---|
| YES 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
| user output |
|---|
| YES 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... Truncated |
Test 14
Group: 3, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
| correct output |
|---|
| NO |
| user output |
|---|
| NO |
Test 15
Group: 1, 2, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 5 6 7 7 6 6 UDUU |
| correct output |
|---|
| YES 1 4 1 1 |
| user output |
|---|
| YES 1 4 1 1 |
Test 16
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 30 15 12 9 88 10 26 78 23 67 14 9... |
| correct output |
|---|
| YES 1 1 1 4 1 3 1 1 7 1 19 1 1 3 1... |
| user output |
|---|
| (empty) |
Test 17
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 1000 1000000 1 146324 146324 289287... |
| correct output |
|---|
| YES 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
| user output |
|---|
| (empty) |
Test 18
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 1000000000 1 421262579 4212625... |
| correct output |
|---|
| YES 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
| user output |
|---|
| (empty) |
Test 19
Group: 1, 2, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 8 1 3 1 2 5 1 1 2 DUUUDUU |
| correct output |
|---|
| NO |
| user output |
|---|
| NO |
Test 20
Group: 2, 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 15 3 1 33 13 1 11 32 8 1 19 15 25... |
| correct output |
|---|
| YES 1 1 5 1 1 3 5 1 1 1 1 5 2 1 |
| user output |
|---|
| (empty) |
Test 21
Group: 2, 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 15 10 2 39 41 42 34 31 28 26 24 2... |
| correct output |
|---|
| YES 1 1 1 1 10 9 8 7 6 1 4 1 1 1 |
| user output |
|---|
| (empty) |
Test 22
Group: 2, 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 15 27 4 6 23 26 37 40 38 44 27 3 ... |
| correct output |
|---|
| YES 1 1 1 1 5 1 7 1 3 1 1 3 1 1 |
| user output |
|---|
| (empty) |
Test 23
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 1000 3246 3562 197273 197429 197755... |
| correct output |
|---|
| YES 1 1 1 4 5 10 3 1 1 3 7 12 1 1 ... |
| user output |
|---|
| (empty) |
Test 24
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 1000 503981 503487 503350 502673 50... |
| correct output |
|---|
| YES 999 1 997 1 1 994 989 1 1 1 1 ... |
| user output |
|---|
| (empty) |
Test 25
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 1000 1445 1363 1749 1084 262408 263... |
| correct output |
|---|
| NO |
| user output |
|---|
| (empty) |
Test 26
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 209655 9167 9389 191291 198294... |
| correct output |
|---|
| NO |
| user output |
|---|
| (empty) |
Test 27
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 16295 14904 5103 13337 26939 3... |
| correct output |
|---|
| YES 1 1 1 1 5 6 1 1 1 10 11 1 13 1... |
| user output |
|---|
| (empty) |
Test 28
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 1859 174288 15040 4631 4993844... |
| correct output |
|---|
| YES 1 3 1 1 99997 99992 1 1 5 1 1 ... |
| user output |
|---|
| (empty) |
Test 29
Group: 5
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 959817 958289 966165 922369 92... |
| correct output |
|---|
| YES 1 1 1 1 1 1 1 1 1 1 11 14 1 1 ... |
| user output |
|---|
| (empty) |
Test 30
Group: 1, 2, 4, 5
Verdict: ACCEPTED
| input |
|---|
| 8 2 3 2 3 5 6 7 8 UDDDUDU |
| correct output |
|---|
| YES 1 2 1 1 5 6 7 |
| user output |
|---|
| YES 3 1 1 2 5 6 7 |