oj.uz

Submission #643065

# Submission time Handle Problem Language Result Execution time Memory
643065 2022-09-21T06:14:17 Z ghostwriter Mechanical Doll (IOI18_doll) C++14
53 / 100
 182 ms 36704 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 = 1e6 + 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 14 ms 23764 KB Output is correct
2 Correct 35 ms 28164 KB Output is correct
3 Correct 31 ms 27604 KB Output is correct
4 Correct 13 ms 23700 KB Output is correct
5 Correct 25 ms 25044 KB Output is correct
6 Correct 43 ms 29652 KB Output is correct
7 Correct 14 ms 23764 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 35 ms 28164 KB Output is correct
3 Correct 31 ms 27604 KB Output is correct
4 Correct 13 ms 23700 KB Output is correct
5 Correct 25 ms 25044 KB Output is correct
6 Correct 43 ms 29652 KB Output is correct
7 Correct 14 ms 23764 KB Output is correct
8 Correct 55 ms 29956 KB Output is correct
9 Correct 59 ms 30828 KB Output is correct
10 Correct 89 ms 33296 KB Output is correct
11 Correct 14 ms 23712 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 13 ms 23708 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 35 ms 28164 KB Output is correct
3 Correct 31 ms 27604 KB Output is correct
4 Correct 13 ms 23700 KB Output is correct
5 Correct 25 ms 25044 KB Output is correct
6 Correct 43 ms 29652 KB Output is correct
7 Correct 14 ms 23764 KB Output is correct
8 Correct 55 ms 29956 KB Output is correct
9 Correct 59 ms 30828 KB Output is correct
10 Correct 89 ms 33296 KB Output is correct
11 Correct 14 ms 23712 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 13 ms 23708 KB Output is correct
14 Correct 91 ms 33900 KB Output is correct
15 Correct 57 ms 29120 KB Output is correct
16 Correct 78 ms 31988 KB Output is correct
17 Correct 13 ms 23764 KB Output is correct
18 Correct 13 ms 23764 KB Output is correct
19 Correct 12 ms 23692 KB Output is correct
20 Correct 80 ms 33348 KB Output is correct
21 Correct 13 ms 23764 KB Output is correct
22 Correct 13 ms 23808 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23764 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 12 ms 23764 KB Output is partially correct
2 Partially correct 148 ms 34596 KB Output is partially correct
3 Partially correct 156 ms 34236 KB Output is partially correct
4 Partially correct 157 ms 35624 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 12 ms 23764 KB Output is partially correct
2 Partially correct 148 ms 34596 KB Output is partially correct
3 Partially correct 156 ms 34236 KB Output is partially correct
4 Partially correct 157 ms 35624 KB Output is partially correct
5 Partially correct 172 ms 36704 KB Output is partially correct
6 Partially correct 164 ms 36372 KB Output is partially correct
7 Partially correct 169 ms 36516 KB Output is partially correct
8 Partially correct 163 ms 36160 KB Output is partially correct
9 Partially correct 141 ms 34176 KB Output is partially correct
10 Partially correct 177 ms 36044 KB Output is partially correct
11 Partially correct 160 ms 35860 KB Output is partially correct
12 Partially correct 167 ms 34324 KB Output is partially correct
13 Partially correct 144 ms 34964 KB Output is partially correct
14 Partially correct 173 ms 34536 KB Output is partially correct
15 Partially correct 148 ms 34696 KB Output is partially correct
16 Partially correct 17 ms 24124 KB Output is partially correct
17 Correct 94 ms 30908 KB Output is correct
18 Partially correct 142 ms 34724 KB Output is partially correct
19 Partially correct 152 ms 34244 KB Output is partially correct
20 Partially correct 163 ms 36024 KB Output is partially correct
21 Partially correct 179 ms 35752 KB Output is partially correct
22 Partially correct 182 ms 35748 KB Output is partially correct