oj.uz

Submission #643062

# Submission time Handle Problem Language Result Execution time Memory
643062 2022-09-21T06:11:48 Z ghostwriter Mechanical Doll (IOI18_doll) C++14
53 / 100
 176 ms 23972 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#include "grader.cpp"
#endif
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
    Tran The Bao
    CTL - Da Lat
    Cay ngay cay dem nhung deo duoc cong nhan
*/
const int MAXM = 4e5 + 5;
int d[MAXM];
namespace subtask123 {
    vi next[MAXM];
    void create_circuit(int M, vi A) {
        vi C(M + 1, 0), X, Y;
        int N = sz(A);
        next[0].pb(A[0]);
        FOR(i, 0, N - 1) next[A[i]].pb(i == N - 1? 0 : A[i + 1]);
        int S = 0;
        FOR(i, 0, M) {
            if (next[i].empty()) {
                C[i] = 0;
                continue;
            }
            if (sz(next[i]) == 1) {
                C[i] = next[i][0];
                continue;
            }
            if (sz(next[i]) == 2) {
                C[i] = --S;
                X.pb(next[i][0]);
                Y.pb(next[i][1]);
                continue;
            }
            if (sz(next[i]) == 3) {
                C[i] = --S;
                X.pb(S - 1);
                Y.pb(S - 2);
                --S;
                X.pb(next[i][0]);
                Y.pb(next[i][1]);
                --S;
                X.pb(S + 2);
                Y.pb(next[i][2]);
                continue;
            }
            C[i] = --S;
            X.pb(S - 1);
            Y.pb(S - 2);
            --S;
            X.pb(next[i][0]);
            Y.pb(next[i][2]);
            --S;
            X.pb(next[i][1]);
            Y.pb(next[i][3]);
        }
        answer(C, X, Y);
    }
}
namespace subtask456 {
    int M, N, S = 0, d[MAXM], d1[MAXM];
    vi A, X, Y;
    void add(int u, int x, int y) {
        WHILE(-u - 1 >= sz(X)) {
            X.pb(0);
            Y.pb(0);
        }
        X[-u - 1] = x;
        Y[-u - 1] = y;
    }
    vi build(int l, int r) {
        if (l == r) return {A[l]};
        int mid = (l + r) / 2 - ((l + r) % 2 == 0? 1 : 0);
        vi left = build(l, mid);
        vi right = build(mid + 1, r);
        int root = --S;
        FOR(i, 1, sz(left) - 1) {
            int u = left[i], &x = X[-u - 1], &y = Y[-u - 1];
            if (x == left[0]) x = root;
            if (y == left[0]) y = root;
        }
        FOR(i, 1, sz(right) - 1) {
            int u = right[i], &x = X[-u - 1], &y = Y[-u - 1];
            if (x == right[0]) x = root;
            if (y == right[0]) y = root;
        }
        if (sz(left) < sz(right)) {
            if (sz(left) == 1) {
                int u = left[0];
                --S;
                add(S, u, root);
                left = {S, S};
            }
            else {
                vi nleft = {left[0]};
                FOR(i, 1, sz(left) - 1) {
                    int u = left[i];
                    int x = X[-u - 1], y = Y[-u - 1];
                    add(u, S - 1, S - 2);
                    nleft.pb(S - 1);
                    nleft.pb(S - 2);
                    --S;
                    add(S, x, root);
                    --S;
                    add(S, y, root);
                }
                swap(left, nleft);
            }
        }
        add(root, left[0], right[0]);
        vi ans = {root};
        FOR(i, 1, sz(left) - 1) ans.pb(left[i]);
        FOR(i, 1, sz(right) - 1) ans.pb(right[i]);
        if (sz(left) == 1) ans.pb(root);
        return ans;
    }
    void create_circuit(int M, vi A) {
        A.pb(0);
        N = sz(A);
        subtask456::M = M;
        subtask456::A = A;
        vi ans = build(0, N - 1);
        int root = ans[0];
        vi C(M + 1);
        FOR(i, 0, M) C[i] = root;
        int cur = 0, cnt = 0;
        WHILE(cnt < N) {
            int pre = cur;
            if (cur >= 0) cur = C[cur];
            else if (!d[-cur - 1]) {
                d[-cur - 1] ^= 1;
                cur = X[-cur - 1];
            }
            else {
                d[-cur - 1] ^= 1;
                cur = Y[-cur - 1];
            }
            if (cur >= 0) {
                cur = A[cnt];
                if (d[-pre - 1]) X[-pre - 1] = A[cnt++];
                else Y[-pre - 1] = A[cnt++];
            }
        }
        answer(C, X, Y);
    }
}
void create_circuit(int M, std::vector<int> A) {
    int N = A.size();
    bool sub123 = 1;
    FOR(i, 0, N - 1) {
        ++d[A[i]];
        if (d[A[i]] > 4) sub123 = 0;
    }
    if (sub123) {
        subtask123::create_circuit(M, A);
        return;
    }
    subtask456::create_circuit(M, A);
}
/*
3 5
5 5 1 1 3
*/

Compilation message

doll.cpp: In function 'void subtask123::create_circuit(int, vi)':
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:46:9: note: in expansion of macro 'FOR'
   46 |         FOR(i, 0, N - 1) next[A[i]].pb(i == N - 1? 0 : A[i + 1]);
      |         ^~~
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:48:9: note: in expansion of macro 'FOR'
   48 |         FOR(i, 0, M) {
      |         ^~~
doll.cpp: In function 'vi subtask456::build(int, int)':
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:105:9: note: in expansion of macro 'FOR'
  105 |         FOR(i, 1, sz(left) - 1) {
      |         ^~~
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:110:9: note: in expansion of macro 'FOR'
  110 |         FOR(i, 1, sz(right) - 1) {
      |         ^~~
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:124:17: note: in expansion of macro 'FOR'
  124 |                 FOR(i, 1, sz(left) - 1) {
      |                 ^~~
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:140:9: note: in expansion of macro 'FOR'
  140 |         FOR(i, 1, sz(left) - 1) ans.pb(left[i]);
      |         ^~~
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:141:9: note: in expansion of macro 'FOR'
  141 |         FOR(i, 1, sz(right) - 1) ans.pb(right[i]);
      |         ^~~
doll.cpp: In function 'void subtask456::create_circuit(int, vi)':
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:153:9: note: in expansion of macro 'FOR'
  153 |         FOR(i, 0, M) C[i] = root;
      |         ^~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:178:5: note: in expansion of macro 'FOR'
  178 |     FOR(i, 0, N - 1) {
      |     ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 27 ms 14484 KB Output is correct
3 Correct 25 ms 14028 KB Output is correct
4 Correct 6 ms 9632 KB Output is correct
5 Correct 13 ms 10868 KB Output is correct
6 Correct 33 ms 16168 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 27 ms 14484 KB Output is correct
3 Correct 25 ms 14028 KB Output is correct
4 Correct 6 ms 9632 KB Output is correct
5 Correct 13 ms 10868 KB Output is correct
6 Correct 33 ms 16168 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 43 ms 16732 KB Output is correct
9 Correct 46 ms 17480 KB Output is correct
10 Correct 71 ms 20780 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 27 ms 14484 KB Output is correct
3 Correct 25 ms 14028 KB Output is correct
4 Correct 6 ms 9632 KB Output is correct
5 Correct 13 ms 10868 KB Output is correct
6 Correct 33 ms 16168 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 43 ms 16732 KB Output is correct
9 Correct 46 ms 17480 KB Output is correct
10 Correct 71 ms 20780 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 86 ms 21312 KB Output is correct
15 Correct 46 ms 15960 KB Output is correct
16 Correct 66 ms 19288 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 7 ms 9708 KB Output is correct
19 Correct 6 ms 9712 KB Output is correct
20 Correct 72 ms 20688 KB Output is correct
21 Correct 5 ms 9708 KB Output is correct
22 Correct 6 ms 9684 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 9684 KB Output is partially correct
2 Partially correct 138 ms 20524 KB Output is partially correct
3 Partially correct 142 ms 21072 KB Output is partially correct
4 Partially correct 154 ms 22936 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 9684 KB Output is partially correct
2 Partially correct 138 ms 20524 KB Output is partially correct
3 Partially correct 142 ms 21072 KB Output is partially correct
4 Partially correct 154 ms 22936 KB Output is partially correct
5 Partially correct 165 ms 23972 KB Output is partially correct
6 Partially correct 159 ms 23760 KB Output is partially correct
7 Partially correct 162 ms 23776 KB Output is partially correct
8 Partially correct 158 ms 23568 KB Output is partially correct
9 Partially correct 145 ms 21008 KB Output is partially correct
10 Partially correct 156 ms 23436 KB Output is partially correct
11 Partially correct 169 ms 23236 KB Output is partially correct
12 Partially correct 142 ms 21060 KB Output is partially correct
13 Partially correct 148 ms 21692 KB Output is partially correct
14 Partially correct 155 ms 21452 KB Output is partially correct
15 Partially correct 148 ms 21548 KB Output is partially correct
16 Partially correct 9 ms 10068 KB Output is partially correct
17 Correct 81 ms 17728 KB Output is correct
18 Partially correct 138 ms 21452 KB Output is partially correct
19 Partially correct 157 ms 21004 KB Output is partially correct
20 Partially correct 162 ms 23416 KB Output is partially correct
21 Partially correct 156 ms 23184 KB Output is partially correct
22 Partially correct 176 ms 23188 KB Output is partially correct