Submission #558415

#	Time	Username	Problem	Language	Result	Execution time	Memory
558415		maomao90	Mechanical Doll (IOI18_doll)	C++17	100 / 100	134 ms	12908 KiB

doll

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;
#include "doll.h"

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 200005

int n, m;
vi a;
int x[MAXN * 2], y[MAXN * 2];
int tog[MAXN * 2];
int lg;

int ptr = 1;
int dnc(int lo, int hi, int k, int n) {
    if (lo == hi) return INF;
    int u = ptr++;
    int mid = lo + hi >> 1;
    if (n >> k & 1 ^ 1) {
        x[u] = -1;
        y[u] = -dnc(mid + 1, hi, k - 1, n);
    } else {
        x[u] = -dnc(lo, mid, k - 1, n);
        y[u] = -dnc(mid + 1, hi, k - 1, (1 << lg) - 1);
    }
    cerr << u << ": " << x[u] << ' ' << y[u] << '\n';
    return u;
}
void sim(int u, int t) {
    tog[u] ^= 1;
    if (tog[u] == 1) {
        if (x[u] == -INF) {
            x[u] = t;
        } else {
            sim(-x[u], t);
        }
    } else {
        if (y[u] == -INF) {
            y[u] = t;
        } else {
            sim(-y[u], t);
        }
    }
}

void create_circuit(int M, vi A) {
    a = A;
    n = A.size();
    m = M;
    a.pb(0);
    vi c(m + 1);
    c[0] = a[0];
    REP (i, 1, m + 1) {
        c[i] = -1;
    }
    if (n == 1) {
        REP (i, 1, m + 1) {
            c[i] = 0;
        }
        vi rx, ry;
        answer(c, rx, ry);
        return;
    }
    lg = 0;
    while ((1 << lg) < n) {
        lg++;
    }
    dnc(0, (1 << lg) - 1, lg - 1, n - 1);
    REP (i, 0, n) {
        sim(1, a[i + 1]);
    }
    vi rx, ry;
    REP (i, 1, ptr) {
        assert(x[i] != -INF && y[i] != -INF);
        rx.pb(x[i]);
        ry.pb(y[i]);
    }
    answer(c, rx, ry);
}

Compilation message (stderr)

doll.cpp: In function 'int dnc(int, int, int, int)':
doll.cpp:48:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int mid = lo + hi >> 1;
      |               ~~~^~~~
doll.cpp:49:16: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   49 |     if (n >> k & 1 ^ 1) {
      |         ~~~~~~~^~~

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