Submission #642879

#	Time	Username	Problem	Language	Result	Execution time	Memory
642879		ghostwriter	Mechanical Doll (IOI18_doll)	C++14	16 / 100	86 ms	13260 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 = 1e5 + 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;
    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;
        vi left = build(l, mid);
        vi right = build(mid + 1, r);
        int root = --S;
        if (sz(left) > sz(right)) {
            if (sz(right) == 1) {
                int u = right[0];
                --S;
                add(S, u, root);
                right = {S, S};
            }
            else {
                vi nright = {right[0]};
                FOR(i, 1, sz(right) - 1) {
                    int u = right[i];
                    int x = X[-u - 1], y = Y[-u - 1];
                    add(u, S - 1, S - 2);
                    nright.pb(S - 1);
                    nright.pb(S - 2);
                    --S;
                    add(S, x, root);
                    --S;
                    add(S, y, root);
                }
                right = nright;
            }
        }
        add(root, left[0], right[0]);
        vi ans = {root};
        EACH(i, left) ans.pb(i);
        EACH(i, right) ans.pb(i);
        return ans;
    }
    void create_circuit(int M, vi A) {
        A.pb(0);
        N = sz(A);
        subtask456::M = M;
        subtask456::A = A;
        build(0, N - 1);
        vi ans = build(0, N - 1);
        int root = ans[0];
        vi C(M + 1);
        FOR(i, 0, M - 1) C[i] = root;
        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);
}
/*
4 4
1 2 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:114:17: note: in expansion of macro 'FOR'
  114 |                 FOR(i, 1, sz(right) - 1) {
      |                 ^~~
doll.cpp:28:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
doll.cpp:130:9: note: in expansion of macro 'EACH'
  130 |         EACH(i, left) ans.pb(i);
      |         ^~~~
doll.cpp:28:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
doll.cpp:131:9: note: in expansion of macro 'EACH'
  131 |         EACH(i, right) ans.pb(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:143:9: note: in expansion of macro 'FOR'
  143 |         FOR(i, 0, M - 1) 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:150:5: note: in expansion of macro 'FOR'
  150 |     FOR(i, 0, N - 1) {
      |     ^~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56