CSES - Datatähti Open 2021 - Results
Submission details
Task:Polygonal Chain
Sender:nigus
Submission time:2021-01-30 18:25:32 +0200
Language:C++ (C++17)
Status:READY
Result:7
Feedback
groupverdictscore
#1ACCEPTED7
#20
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 4, 5details
#2ACCEPTED0.01 s1, 2, 4, 5details
#3ACCEPTED0.01 s1, 2, 4, 5details
#4ACCEPTED0.93 s1, 2, 4, 5details
#5ACCEPTED0.01 s1, 2, 4, 5details
#60.40 s2, 4, 5details
#70.40 s2, 4, 5details
#80.28 s2, 4, 5details
#90.29 s2, 4, 5details
#10ACCEPTED0.38 s2, 4, 5details
#110.05 s4, 5details
#12--5details
#130.07 s3, 4, 5details
#14ACCEPTED0.07 s3, 4, 5details
#15ACCEPTED0.01 s1, 2, 4, 5details
#160.12 s4, 5details
#170.05 s4, 5details
#18--5details
#19ACCEPTED0.39 s1, 2, 4, 5details
#200.39 s2, 4, 5details
#210.40 s2, 4, 5details
#220.40 s2, 4, 5details
#230.04 s4, 5details
#240.05 s4, 5details
#25ACCEPTED0.05 s4, 5details
#26--5details
#27--5details
#28--5details
#29--5details
#30ACCEPTED0.01 s1, 2, 4, 5details

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

user output
YES

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:

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:

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:

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:

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:

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:

input
100000
999999998 999999996 999999994 ...

correct output
YES
99997 99995 99993 99991 99989 ...

user output
(empty)

Test 13

Group: 3, 4, 5

Verdict:

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:

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:

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:

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:

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:

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:

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:

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:

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:

input
100000
209655 9167 9389 191291 198294...

correct output
NO

user output
(empty)

Test 27

Group: 5

Verdict:

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:

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:

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