Submission #1077255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077255		onbert	Mechanical Doll (IOI18_doll)	C++17	53 / 100	121 ms	19704 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5, maxm = 1e5 + 5, maxN = 4e5 + 5;
int n, m;
vector<int> a;
int cnt = 0;
vector<int> adj[maxm];
vector<int> nxt, l, r;
bool on[maxN];

void build(int u, int sz) {
    if (sz == 1) return;
    l.push_back(0), r.push_back(0);
    l.push_back(0), r.push_back(0);
    cnt--, l[-u-1] = cnt;
    cnt--, r[-u-1] = cnt;
    build(l[-u-1], sz-1); build(r[-u-1], sz-1);
}

void create_circuit(int M, vector<int> A) {
    m = M, a = A;
    n = a.size();
    for (int i=0;i<n-1;i++) adj[a[i]].push_back(a[i+1]);
    adj[a[n-1]].push_back(0);
    nxt.resize(m+1);
    nxt[0] = a[0];
    for (int i=1;i<=m;i++) {
        // cout << i << endl;
        if (adj[i].size()==0) continue;
        if (adj[i].size()==1) {
            nxt[i] = adj[i][0];
            continue;
        }
        cnt--;
        l.push_back(0), r.push_back(0);
        // cout << cnt << " " << l.size() << " " << r.size() << endl;
        int rt = cnt;
        nxt[i] = cnt;
        int sz = log2(adj[i].size() - 1) + 1;
        build(rt, sz);
        sz = (1<<sz);
        int delta = sz - adj[i].size();
        // cout << delta << endl;
        // cout << i << endl;
        // for (int x:adj[i]) cout << x << " "; cout << endl;
        for (int j=0;j<sz;j++) {
            int u = rt;
            while (l[-u-1] != 0 && r[-u-1] != 0) {
                if (on[-u-1]) {
                    on[-u-1] = !on[-u-1];
                    u = r[-u-1];
                } else {
                    on[-u-1] = !on[-u-1];
                    u = l[-u-1];
                }
            }
            // cout << u << " " << on[u] << " " << j << " " << j-delta << " " << adj[i][j-delta] << endl;
            if (on[-u-1]) {
                on[-u-1] = !on[-u-1];
                if (j-delta < 0) r[-u-1] = rt;
                else r[-u-1] = adj[i][j-delta];
            } else {
                on[-u-1] = !on[-u-1];
                if (j-delta < 0) l[-u-1] = rt;
                else l[-u-1] = adj[i][j-delta];
            }
        }
        // cout << l.size() << endl;
        // for (int j=0;j<l.size();j++) cout << l[j] << " " << r[j] << endl;
    }
    // cout << l.size() << endl;
    // for (int i=0;i<l.size();i++) cout << l[i] << " " << r[i] << endl;
    // int u = 0;
    // while (true) {
    //     // if (u>=0) cout << u << endl;
    //     if (u>=0) u = nxt[u];
    //     else if (on[-u-1]) {
    //         on[-u-1] = !on[-u-1];
    //         u = r[-u-1];
    //     } else {
    //         on[-u-1] = !on[-u-1];
    //         u = l[-u-1];
    //     }
    //     if (u==0) break;
    // }
    answer(nxt, l, r);
}

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