Task: | Polygonal Chain |
Sender: | nigus |
Submission time: | 2021-01-30 18:25:32 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 7 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 7 |
#2 | WRONG ANSWER | 0 |
#3 | WRONG ANSWER | 0 |
#4 | WRONG ANSWER | 0 |
#5 | WRONG ANSWER | 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.93 s | 1, 2, 4, 5 | details |
#5 | ACCEPTED | 0.01 s | 1, 2, 4, 5 | details |
#6 | WRONG ANSWER | 0.40 s | 2, 4, 5 | details |
#7 | WRONG ANSWER | 0.40 s | 2, 4, 5 | details |
#8 | WRONG ANSWER | 0.28 s | 2, 4, 5 | details |
#9 | WRONG ANSWER | 0.29 s | 2, 4, 5 | details |
#10 | ACCEPTED | 0.38 s | 2, 4, 5 | details |
#11 | WRONG ANSWER | 0.05 s | 4, 5 | details |
#12 | TIME LIMIT EXCEEDED | -- | 5 | details |
#13 | WRONG ANSWER | 0.07 s | 3, 4, 5 | details |
#14 | ACCEPTED | 0.07 s | 3, 4, 5 | details |
#15 | ACCEPTED | 0.01 s | 1, 2, 4, 5 | details |
#16 | WRONG ANSWER | 0.12 s | 4, 5 | details |
#17 | WRONG ANSWER | 0.05 s | 4, 5 | details |
#18 | TIME LIMIT EXCEEDED | -- | 5 | details |
#19 | ACCEPTED | 0.39 s | 1, 2, 4, 5 | details |
#20 | WRONG ANSWER | 0.39 s | 2, 4, 5 | details |
#21 | WRONG ANSWER | 0.40 s | 2, 4, 5 | details |
#22 | WRONG ANSWER | 0.40 s | 2, 4, 5 | details |
#23 | WRONG ANSWER | 0.04 s | 4, 5 | details |
#24 | WRONG ANSWER | 0.05 s | 4, 5 | details |
#25 | ACCEPTED | 0.05 s | 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 |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:87:14: warning: unused variable 'd' [-Wunused-variable] ll a,b,c,d; ^
Code
#pragma GCC optimize("O3") //#include <bits/stdc++.h>using namespace std;#define rep(i, a, b) for(int i = a; i < (b); ++i)#define per(i, b, a) for(int i = b - 1; i >= a; i--)#define trav(a, x) for(auto& a : x)#define all(x) x.begin(), x.end()#define sz(x) (int)(x).size()typedef long long ll;typedef pair<int, int> pii;typedef pair<ll, ll> pll;typedef vector<int> vi;typedef vector<ll> vl;typedef long double ld;typedef unsigned long long ull;unsigned seed = chrono::system_clock::now().time_since_epoch().count();mt19937 eng(seed);ll random2(){return (1ll << 31ll)*eng()+eng();}ll n,m,k,q,T;const ll big = 1000000007;const ll big2 = 1000000009;const ll mod = 998244353;const int MAXN = 200002;string dirs;vl X;vl Y;bool bad(int i, int j){if(i == n)return 0;if(j == 0)return 0;ll mi = min(X[i+1], X[i]);ll ma = max(X[i+1], X[i]);if(X[j] < mi || X[j] > ma)return 0;return 1;}bool bad2(int i, int j){if(!bad(i, j))return 0;if(i == j-1 || i == j)return 0;if(Y[i] < min(Y[j-1], Y[j]))return 0;if(Y[i] > max(Y[j-1], Y[j]))return 0;return 1;}bool valid(){rep(c1,0,n-1){if(dirs[c1] == 'U'){if(Y[c1] >= Y[c1+1])return 0;}else{if(Y[c1] <= Y[c1+1])return 0;}}return 1;}int bads(){int res = 0;rep(c1,0,n){rep(c2,0,n){if(c1 != c2){res += bad2(c1,c2);}}}if(!valid())return 12543543;return res;}int main() {ios_base::sync_with_stdio(0);cin.tie(0);//freopen("fhc.txt","r",stdin);//freopen("autput.txt","w",stdout);ll a,b,c,d;cin >> n;X.push_back(0);rep(c1,0,n){cin >> a;if(c1%2 == 1)a = -a;X.push_back(X[c1]+a);}cin >> dirs;rep(c1,0,n){Y.push_back(c1);}ll L = 0;ll R = n-1;for(int c1 = n-1; c1 >= 0; c1--){if(c1 == 0){Y[c1] = R;break;}if(dirs[c1-1] == 'U'){Y[c1] = R;R--;}else{Y[c1] = L;L++;}}int lim = 10000000/(n*n);b = -1;for(int c4 = 0; c4 < lim; c4++){if(c4%100 == 0){random_shuffle(all(Y));b = -1;}if(b == -1)b = bads();if(b == 0)break;int l,r;rep(c1,0,100){l = random2()%n;r = random2()%n;if(l == r)continue;swap(Y[l], Y[r]);if(!valid()){swap(Y[l], Y[r]);continue;}break;}c = bads();if(c >= b){swap(Y[l], Y[r]);}else{b = -1;}}if(bads() == 0){cout << "YES\n";rep(c1,0,n-1){cout << abs(Y[c1+1]-Y[c1]) << " ";}cout << "\n";}else{cout << "NO\n";}return 0;}
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 4 1 1 7 |
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 4 1 2 3 1 5 |
Test 6
Group: 2, 4, 5
Verdict: WRONG ANSWER
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 |
---|
NO |
Test 7
Group: 2, 4, 5
Verdict: WRONG ANSWER
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 |
---|
NO |
Test 8
Group: 2, 4, 5
Verdict: WRONG ANSWER
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 |
---|
NO |
Test 9
Group: 2, 4, 5
Verdict: WRONG ANSWER
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 |
---|
NO |
Test 10
Group: 2, 4, 5
Verdict: ACCEPTED
input |
---|
15 100 2 99 1 78 4 93 2 100 1 15 ... |
correct output |
---|
NO |
user output |
---|
NO |
Test 11
Group: 4, 5
Verdict: WRONG ANSWER
input |
---|
1000 999997 999995 999993 999991 99... |
correct output |
---|
YES 997 995 993 991 989 987 985 98... |
user output |
---|
NO |
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: WRONG ANSWER
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 |
---|
NO |
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: WRONG ANSWER
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 |
---|
NO |
Test 17
Group: 4, 5
Verdict: WRONG ANSWER
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 |
---|
NO |
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: WRONG ANSWER
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 |
---|
NO |
Test 21
Group: 2, 4, 5
Verdict: WRONG ANSWER
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 |
---|
NO |
Test 22
Group: 2, 4, 5
Verdict: WRONG ANSWER
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 |
---|
NO |
Test 23
Group: 4, 5
Verdict: WRONG ANSWER
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 |
---|
NO |
Test 24
Group: 4, 5
Verdict: WRONG ANSWER
input |
---|
1000 503981 503487 503350 502673 50... |
correct output |
---|
YES 999 1 997 1 1 994 989 1 1 1 1 ... |
user output |
---|
NO |
Test 25
Group: 4, 5
Verdict: ACCEPTED
input |
---|
1000 1445 1363 1749 1084 262408 263... |
correct output |
---|
NO |
user output |
---|
NO |
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 |