Submission #573293

#	Time	Username	Problem	Language	Result	Execution time	Memory
573293		MadokaMagicaFan	Mechanical Doll (IOI18_doll)	C++14	6 / 100	93 ms	14364 KiB

doll

#include "bits/stdc++.h"

using namespace std;

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

#define all(v)                      v.begin(), v.end()
#define rall(v)                     v.rbegin(), v.rend()
#define sz(v)                       ((int)v.size())

#define forn(i,n)                   for(int i = 0; i < n; ++i)
#define forbe(i,b,e)                for(int i = b; i < e; ++i)

#define pb                          push_back

#define pry                         puts("YES")
#define prn                         puts("NO")
#define endl                        '\n'

#define fst                         first
#define scn                         second

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

vector<int> etrig[M+1];
vector<int> X;
vector<int> Y;
int cnt = 1;

int
dfs(int x, int s, int k)
{
    if ((sz(etrig[x])-s-1)/(1<<k) == 0) return etrig[x][s];
    int size = 1 + (sz(etrig[x])-s-1)/(1<<k);
    if (size&1)
        assert(0);
    int _y = dfs(x,s+(1<<k),k+1);
    int _x = dfs(x,s,k+1);
    if (_x == _y)
        return _x;
    X.pb(0);
    Y.pb(0);
    Y[cnt-1] = _y;
    X[cnt-1] = _x;
    ++cnt;

    return -(cnt-1);
}

int
donode(int x)
{
    int scount = cnt++;
    X.pb(0);
    Y.pb(0);

    int last = 0;
    for (int j = 0; j < 20; ++j) {
        if (sz(etrig[x])&(1<<j))
            last = j;
    }

    if (sz(etrig[x]) != (1<<last))
        ++last;
    if (sz(etrig[x]) < (1<<last)) {
        X.pb(0);
        Y.pb(0);
        X[cnt-1] = -cnt;
        Y[cnt-1] = -scount;
        while (sz(etrig[x]) < (1<<last))
            etrig[x].pb(-cnt);
        ++cnt;
    }

    X[scount-1] = dfs(x,0,1);
    Y[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);

    for (int i = 0; i < n-1; ++i) {
        etrig[a[i]].pb(a[i+1]);
        assert(a[i] != 0);
    }
    etrig[a[n-1]].pb(0);

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

    answer(trigexit,X,Y);
    return;
}

#ifdef ONPC
void 
answer(vector<int> c, vector<int> X, vector<int> Y)
{
    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] << endl;
        cout << i+1 << ": " << Y[i] << endl;
    }
}

void
solve()
{
    int m = 10;
    vector<int> c = {1, 2, 10, 1, 3, 1, 4, 1, 5, 1, 6,1, 7};
    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