Submission #574158

#	Time	Username	Problem	Language	Result	Execution time	Memory
574158		MadokaMagicaFan	Mechanical Doll (IOI18_doll)	C++14	6 / 100	92 ms	17876 KiB

doll

#include "bits/stdc++.h"
/* #include "doll.h" */

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define sz(v)                       ((int)v.size())

#define pb                          push_back
#define endl                        '\n'

#define fst                         first
#define scn                         second

const int N = 2e5;
const int M = 2e5;

vector<int> etrig[M+2];
vector<int> ansX;
vector<int> ansY;

const ll P = 2e7;
const ll S = 4e5;

ll p = 0;

int
addindex()
{
    ansX.pb(0);
    ansY.pb(0);
    return sz(ansX);
}

int
dfs(int x, ll s, int k)
{
    assert(x < M+2);
    assert(x > -1);
    assert(s > -1);
    assert(k > -1);
    assert(s<sz(etrig[x]));

    /* int size = 1 + (sz(etrig[x])-s-1)/(1<<k); */
    if (s+(1l<<k)>=sz(etrig[x])) return etrig[x][s];
    /* if (size&1) */
    /*     assert(0); */
    int _x = dfs(x,s,k+1);
    int _y = dfs(x,s+(1<<k),k+1);
    if (_x == _y)
        return _x;

    /* p += size; */
    int indx = addindex();
    assert(indx-1>-1);
    assert(indx-1<sz(ansX));
    assert(indx-1<sz(ansY));
    ansY[indx-1] = _y;
    ansX[indx-1] = _x;

    return -indx;
}

int
donode(int x)
{
    assert(x < M+2);
    if (sz(etrig[x]) == 1)
        return etrig[x][0];
    int scount = addindex();

    int last = 31 - __builtin_clz(sz(etrig[x]));
    assert(last > 0);

    last = (1<<last);

    if (sz(etrig[x]) != last) {
        last <<= 1;
        int temp = etrig[x][sz(etrig[x])-1];
        etrig[x][sz(etrig[x])-1] = -scount;
        while (sz(etrig[x]) < last)
            etrig[x].pb(-scount);
        assert(last-1 < sz(etrig[x]));
        etrig[x][last-1] = temp;
    }

    p += (1<<last);

    assert(scount-1 > -1);
    assert(scount-1<sz(ansX));
    assert(scount-1<sz(ansY));
    ansX[scount-1] = dfs(x,0,1);
    ansY[scount-1] = dfs(x,1,1);


    return -scount;
}

void answer(vector<int> c, vector<int> X, vector<int> Y);

void
create_circuit(int m, vector<int> a)
{
    int n = sz(a);
    vector<int> trigexit(m+1,0);
    ansX.clear();
    ansY.clear();
    for (int i = 0; i <= m; ++i)
        etrig[i].clear();
    assert(m<M+2);


    for (int i = 0; i < n-1; ++i) {
        assert(a[i]<M+2);
        assert(a[i]>-1);
        etrig[a[i]].pb(a[i+1]);
        /* assert(a[i] != 0); */
    }
    /* assert(a[n-1] != 0); */
    assert(n-1<sz(a));
    assert(n>0);
    assert(a[n-1]<M+2);
    assert(a[n-1]>-1);
    etrig[a[n-1]].pb(0);

    trigexit[0] = a[0];
    for (int i = 1; i <= m; ++i) {
        assert(i < sz(trigexit));
        assert(i > -1);
        if (sz(etrig[i]) == 0) {
            trigexit[i] = 0;
        } else {
            trigexit[i] = donode(i);
        }
    }

    vector<int> realX(sz(ansX));
    vector<int> realY(sz(ansX));

    for (int i = 0; i < sz(ansX); ++i) {
        realX[i] = ansX[i];
        realY[i] = ansY[i];
    }

    /* if (cnt > S) { */
    /*     cout << "S: " << cnt << endl; */
    /* } */
    /* assert(cnt <= S); */
    /* if (p > P) { */
    /*     cout << "P: " << p << endl; */
    /* } */
    /* assert(p <= P); */

    answer(trigexit,realX,realY);
    return;
}

#ifdef ONPC
void 
answer(vector<int> c, vector<int> X, vector<int> Y)
{
    vector<bool> state(sz(X));
    vector<int> ans;
    /* for (int i = 0; i < sz(c); ++i) { */
    /*     cout << i << ": " << c[i] << endl; */
    /* } */
    /* for (int i = 0; i < sz(X); ++i) { */
    /*     cout << i+1 << ": " << X[i] << ' ' << Y[i] << endl; */
    /* } */
    int trg = c[0];
    do {
        if (trg >= 0) {
            ans.pb(trg);
            trg = c[trg];
        } else {
            int indx = abs(trg)-1;
            if (!state[indx]) trg = X[indx];
            else trg = Y[indx];
            state[indx] = !state[indx];
        }
    } while (trg != 0);

    for (int i = 0; i < sz(X); ++i) {
        if (state[i]) {
            cout << 10 << endl;
            /* cout << "0\n"; */
            return;
        }
    }
    
    for (int i = 0; i < sz(ans); ++i) {
        cout << ans[i] << ' ';
    }
    cout << endl;
}

void
solve()
{
    int m,n;
    cin >> m >> n;
    vector<int> c(n);
    for (int i = 0; i < n; ++i) {
        cin >> c[i];
    }
    cout << m << ' ' << n << endl;
    /* vector<int> c = {1,2,1}; */
    create_circuit(m,c);
}

int32_t
main()
{
    /* freopen("in", "r", stdin); */
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

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