CSES - Datatähti Open 2021 - Results
Submission details
Task:Polygonal Chain
Sender:endagorion
Submission time:2021-01-31 10:33:08 +0200
Language:C++17
Status:READY
Result:26
Feedback
groupverdictscore
#1ACCEPTED7
#2ACCEPTED19
#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.01 s1, 2, 4, 5details
#5ACCEPTED0.01 s1, 2, 4, 5details
#6ACCEPTED0.01 s2, 4, 5details
#7ACCEPTED0.01 s2, 4, 5details
#8ACCEPTED0.01 s2, 4, 5details
#9ACCEPTED0.01 s2, 4, 5details
#10ACCEPTED0.01 s2, 4, 5details
#110.01 s4, 5details
#120.01 s5details
#130.01 s3, 4, 5details
#140.01 s3, 4, 5details
#15ACCEPTED0.01 s1, 2, 4, 5details
#160.01 s4, 5details
#170.01 s4, 5details
#180.01 s5details
#19ACCEPTED0.01 s1, 2, 4, 5details
#20ACCEPTED0.01 s2, 4, 5details
#21ACCEPTED0.01 s2, 4, 5details
#22ACCEPTED0.01 s2, 4, 5details
#230.01 s4, 5details
#240.01 s4, 5details
#250.01 s4, 5details
#260.01 s5details
#270.01 s5details
#280.01 s5details
#290.01 s5details
#30ACCEPTED0.01 s1, 2, 4, 5details

Code

#include <bits/stdc++.h>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int maxn = 16;
int l[maxn], x[maxn], h[maxn];
string vdir;

int dp[1 << maxn], prv[1 << maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "rt", stdin);
#endif

    int n;
    cin >> n;
    forn(i, n) cin >> l[i];
    x[0] = 0;
    forn(i, n) x[i + 1] = x[i] + l[i] * (i % 2 == 0 ? 1 : -1);

    cin >> vdir;

    dp[0] = 1;
    forn(mask, 1 << n) {
        if (!dp[mask]) continue;
//        cerr << mask << ' ';
        forn(i, n) {
            if ((mask >> i) & 1) continue;
            bool ok = true;
            if (i) ok &= ((mask >> (i - 1)) & 1) == int(vdir[i - 1] == 'U');

            int l = x[i], r = x[i + 1];
            if (l > r) swap(l, r);
            for1(j, n - 1) {
                if (j == i + 1 || j == i) continue;
                if (x[j] < l || x[j] > r) continue;
                ok &= ((mask >> (j - 1)) & 1) == ((mask >> j) & 1);
            }

            if (ok) {
                dp[mask | (1 << i)] = 1;
                prv[mask | (1 << i)] = i;
            }
        }
    }

    if (!dp[(1 << n) - 1]) cout << "NO\n";
    else {
        int mask = (1 << n) - 1;
        ford(y, n) {
            int b = prv[mask];
            h[b] = y;
            mask ^= 1 << b;
        }

        cout << "YES\n";
        forn(i, n - 1) {
            cout << (h[i + 1] - h[i]) * (vdir[i] == 'U' ? 1 : -1) << ' ';
        }
        cout << '\n';
    }

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    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 5 1 1 1 1 5 

Test 6

Group: 2, 4, 5

Verdict: ACCEPTED

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
YES
1 2 7 1 5 1 1 1 1 8 1 3 1 1 

Test 7

Group: 2, 4, 5

Verdict: ACCEPTED

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
YES
1 1 3 1 1 1 1 3 1 1 3 3 1 1 

Test 8

Group: 2, 4, 5

Verdict: ACCEPTED

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
YES
1 2 3 4 5 6 14 1 6 5 4 3 2 1 

Test 9

Group: 2, 4, 5

Verdict: ACCEPTED

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
YES
13 11 9 7 5 3 1 1 3 5 7 9 11 1...

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
(empty)

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
(empty)

Test 14

Group: 3, 4, 5

Verdict:

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
NO

user output
(empty)

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
(empty)

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
(empty)

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: ACCEPTED

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
YES
1 1 5 1 1 3 5 1 1 1 1 5 2 1 

Test 21

Group: 2, 4, 5

Verdict: ACCEPTED

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
YES
1 1 1 1 10 9 8 7 6 1 4 1 1 1 

Test 22

Group: 2, 4, 5

Verdict: ACCEPTED

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
YES
1 1 1 1 5 3 1 1 11 1 3 1 1 3 

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
(empty)

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
(empty)

Test 25

Group: 4, 5

Verdict:

input
1000
1445 1363 1749 1084 262408 263...

correct output
NO

user output
(empty)

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
1 2 1 1 5 6 7