Submission #416896

#	Time	Username	Problem	Language	Result	Execution time	Memory
416896		balbit	Mechanical Doll (IOI18_doll)	C++14	53 / 100	169 ms	22744 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
//#define BALBIT
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define f first
#define s second

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()


#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)

template<typename T> void _do(T && x) { cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S &&...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)

#endif // BALBIT

const int maxn = 2e5+5;

vector<int> go[maxn];

int IT = 0; // keep indexes positive until returning

vector<int> X,Y;
vector<int> sw;
bool st[maxn*4];

//int add(int x=0, int y=0) {
//    X.pb(x); Y.pb(y);
//    return ++IT;
//}

const int inf = 1000000000;

void create_circuit(int n, std::vector<int> A) {
    bug("HI");
    X.pb(0); Y.pb(0);
    A.pb(0);
    int m = SZ(A);
    REP(i, m-1) {
        go[A[i]].pb(A[i+1]);
    }
    sw.resize(n+1);
    sw[0] = A[0];
    REP1(i,n) {
        if (SZ(go[i]) == 0) {
            sw[i] = i;
            continue;
        }
        if (SZ(go[i]) == 1) {
            sw[i] = go[i][0];
            continue;
        }
        int dep = 0;
        while ((1<<dep) < SZ(go[i])) ++dep;
        bug(i, SZ(go[i]), dep);
        // build tree
        sw[i] = -(IT+1);
        REP1(j, (1<<dep)-1) {
            X.pb(0); Y.pb(0);
            int lc = j*2, rc = j*2+1;
            if (lc < (1<<dep)) {
                X[j+IT] = -(lc+IT); Y[j+IT] = -(rc+IT);
            }else{
                X[j+IT] = Y[j+IT] = inf;
            }
        }
        IT += ((1<<dep)-1);
        vector<int> hi;
        REP(j, (1<<dep) - SZ(go[i])) hi.pb(sw[i]);
        for (int x : go[i]) hi.pb(x);
        REP(j, (1<<dep)) {
            int at = -sw[i];
            while (1) {
                int &to = st[at]?Y[at]:X[at];
                st[at] ^= 1;
                if (to == inf) {
                    to = hi[j];
                    break;
                }else{
                    at = -to;
                }
            }
        }
    }
    X.erase(X.begin()); Y.erase(Y.begin());
    answer(sw,X,Y);
}


/*
3 6
1 2 1 3 2 1
*/

• 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