Submission #577564

#	Time	Username	Problem	Language	Result	Execution time	Memory
577564		MadokaMagicaFan	Mechanical Doll (IOI18_doll)	C++14	78.40 / 100	251 ms	21732 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 sz(v)                       ((int)v.size())
#define pb                          push_back

#define pry                         cout << "YES\n"
#define prn                         cout << "NO\n"
#define endl                        '\n'

#define fst                         first
#define scn                         second
/* #define ONPC */

const int M = 1e5;
vector<int> v[M+5], x, y, c;
const int S = 4e5;
const int P = 2e7;
vector<int> reala;
map<int,int> compress;
int p = 0;

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

int
news()
{
    x.pb(0);
    y.pb(0);
    return sz(x);
}

void
dfs2(int l, int r, int s, int k)
{
    if (l == r) {
        reala[l] = s;
        return;
    }
    int mid = (l+r)>>1;
    dfs2(l,mid,s,k+1);
    dfs2(mid+1,r,s+(1<<k),k+1);
}

int
dfs(int l, int r, int ind, vector<int>& a,int k)
{
    if (l == r) {
        if (l >= sz(a)-1) {
            if (l == (1<<x[ind-1])-1)
                return a[sz(a)-1];
            else
                return -ind;
        }
        return a[compress[reala[l]]];
    }

    int mid = (l+r)>>1;
    int _x = dfs(l,mid,ind,a,k+1);
    int _y = dfs(mid+1,r,ind,a,k+1);
    if (_x == _y)
        return _x;
    int index = news();
    p += (1<<(x[ind-1]-k));
    x[index-1] = _x;
    y[index-1] = _y;

    return -index;
}

int
donode(vector<int> &a)
{
    if (sz(a) == 1) return 0;
    int l = 31 - __builtin_clz(sz(a));
    if (sz(a) != (1<<l))
        ++l;
    int ind = news();
    x[ind-1] = l;
    p += (1<<(l));

    reala.resize(1<<l);
    dfs2(0,(1<<l)-1,0,0);
    vector<int> normalization;
    for (int i = 0; i < sz(a)-1; ++i) {
        normalization.pb(reala[i]);
    }
    sort(normalization.begin(), normalization.end());
    for (int i = 0; i < sz(a)-1; ++i) {
        compress[normalization[i]] = i;
    }


    int mid = ((1<<l)-1)>>1;
    int _x = dfs(0,mid,ind,a,1);
    int _y = dfs(mid+1,(1<<l)-1,ind,a,1);

    x[ind-1] = _x;
    y[ind-1] = _y;

    return -ind;
}

void
create_circuit(int m, vector<int> a)
{
    int n = sz(a);
    vector<int> a2;
    for (int j = 1; j < n; ++j) {
        a2.pb(a[j]);
    }
    a2.pb(0);
    
    int indx = donode(a2);

    c.assign(m+1,indx);
    c[0] = a[0];


    /* assert(sz(x)<=n*2); */
    /* cout << sz(x) << ' ' << n << ' ' << n + 31 - __builtin_clz(n) << endl; */
    /* return; */
    assert(sz(x)<=S);
    /* assert(sz(x)<=n+log2(n)); */
    /* return; */
    assert(p<=P);
    answer(c,x,y);

    return;
}


#ifdef ONPC
void
answer(vector<int> C, vector<int> X, vector<int> Y)
{
    int s = sz(X);
    int m = sz(C)-1;

    for (int i = 0; i < sz(C); ++i) {
        assert(C[i] <= m);
        assert(C[i] >= -s);
    }
    for (int i = 0; i < sz(X); ++i) {
        assert(X[i] <= m);
        assert(X[i] >= -s);
        assert(Y[i] <= m);
        assert(Y[i] >= -s);
    }

    vector<int> ans;
    vector<bool> state(sz(X),0);

    /* for (int i = 0; i < sz(X); ++i) { */
    /*     cout << "-" << i+1 << ": " << X[i] << ' ' << Y[i]<< endl; */
    /* } */

    int tg = C[0];

    while (tg) {
        if (tg >= 0) {
            ans.pb(tg);
            tg = C[tg];
        } else {
            int index = -tg-1;
            if (state[index]==0) tg = X[index];
            else                 tg = Y[index];
            state[index] = !state[index];
        }
    }

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

void
solve()
{
    int n, m;
    cin >> m;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    
    cout << m << ' ';
    create_circuit(m, a);
}

int32_t
main(int argc, char **argv)
{
    if (argc >= 2) {
        freopen(argv[1], "r", stdin);
    } else
        ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

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