Submission #643062

#	Time	Username	Problem	Language	Result	Execution time	Memory
643062		ghostwriter	Mechanical Doll (IOI18_doll)	C++14	53 / 100	176 ms	23972 KiB

doll

#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 (stderr)

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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9 / 18
• Subtask 6: 28 / 56