Submission #1217427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217427		perekopskad	Mechanical Doll (IOI18_doll)	C++20	85.55 / 100	147 ms	14408 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define el '\n'
#define pb push_back
#define pii pair <ll, ll>
#define ff first
#define ss second
#define mkp make_pair
#define fr(i, l, r) for(ll (i) = l; (i) <= r; (i)++)
#define frb(i, r, l) for(ll (i) = r; (i) >= l; (i)--)

template<class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}

template<class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}

ll const N = 1e5 + 10;
ll const LOG = 22;
ll const inf = 1e9 + 10;
ll const INF = 1e18 + 10;
ll const mod = 1e9 + 7;
ll const mod2 = 998244353;
ll const K = 400;

vector <int> g[N], c, x, y;
ll cur = 0;

vector <pii> fll;

void gofuck(ll i, ll st, ll l, ll r, ll left) {
    ll mid = (l + r) / 2;
    
    if(mid <= left)
        x[i - 1] = st;
    else {
        if(l < mid) {
            x.pb(0);
            y.pb(0);
            ++cur;
            x[i - 1] = -cur;
            gofuck(cur, st, l, mid, left);
        }
        else {
            fll.pb({2 * (i - 1), l - 1});
        }
    }
    if(mid + 1 < r) {
        x.pb(0);
        y.pb(0);
        ++cur;
        y[i - 1] = -cur;
        gofuck(cur, st, mid + 1, r, left);
    }
    else {
        fll.pb({2 * (i - 1) + 1, mid});
    }
}

bool comp(pii a, pii b) {
    while(a.ss || b.ss) {
        if(a.ss % 2 != b.ss % 2)
            return a.ss % 2 < b.ss % 2;
        a.ss /= 2; b.ss /= 2;
    }
    return 0;
}

void build(ll v) {
    ll s = g[v].size();
    if(!s) return;
    if(s == 1) {
        c[v] = g[v][0];
        return;
    }
    ll val = __lg(2 * s - 1);
    val = (1 << val);

    ll left = val - s;
    x.pb(0); y.pb(0);
    ++cur;
    c[v] = -cur;
    gofuck(cur, -cur, 1, val, left);

    sort(fll.begin(), fll.end(), comp);
    ll it = 0;
    for(auto [u, l] : fll) {
        ll id = u / 2;
        if(u % 2 == 0) {
            x[id] = g[v][it];
        }
        else {
            y[id] = g[v][it];
        }
        it++;
    }
    fll.clear();
}

void create_circuit(int M, std::vector<int> A) {
    c.resize(M + 1);
    g[0].pb(A[0]);
    fr(i, 1, A.size() - 1)
        g[A[i - 1]].pb(A[i]);

    g[A.back()].pb(0);

    fr(v, 0, M) {
        build(v);
    }
    answer(c, x, y);
}

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