Submission #525086

#	Time	Username	Problem	Language	Result	Execution time	Memory
525086		Redhood	Mechanical Doll (IOI18_doll)	C++14	6 / 100	118 ms	24728 KiB

doll

#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define pb push_back

#include "doll.h"
typedef long long ll;
typedef long double ld;

using namespace std;
const int N = (int)5e5 + 10;

int lst = 0;
vector<int>trans[N];
int m;
int x[N],y[N];
int build(vector<int>k, int ROOT){
    if(sz(k) == 1){
        if(k[0] == -1){
            x[lst]=lst;
            y[lst]=ROOT;
            lst++;
            return lst-1;
        }
        return k[0];
    }
//    assert(sz(k) != 0);
    vector<int>st[2];
    if(sz(k) % 2 != 0)
        k.insert(k.begin(), -1);
    for(int i = 0; i < sz(k); ++i)
        st[i&1].pb(k[i]);

//    if(sz(st[0])>sz(st[1])){
//        st[1].insert(st[1].begin(),-1);
//    }
    int v = lst++;
    if(ROOT==-1){
        ROOT = v;
    }

    int A=build(st[0],ROOT),B=build(st[1],ROOT);
    x[v]=A;
    y[v]=B;
    return v;
}
int code(int f){
    if(f <= m)
        return f;
    return -(f-m);
}
bool good(int f){
    int pw=1;
    int F = f;
    while(f){
        f>>=1;
        pw<<=1;
    }
    pw>>=1;
    if(pw==F)
        return true;
    return false;
}
void create_circuit(int M, std::vector<int> A){
    for(int i=0;i<=M;++i)
        trans[i].clear();
    lst=0;
    m = M;
    A.push_back(0);


    A.insert(A.begin(), 0);
    for(int i = 0; i < sz(A) - 1; ++i){
        trans[A[i]].push_back(A[i + 1]);
    }
    lst = M + 1;
    vector < int > C(M + 1);

    for(int i = 0; i <= M; ++i){
        if(sz(trans[i]) == 0)
            continue;
//        reverse(all(trans[i]));
//        while(!good(sz(trans[i]))){
//            trans[i].pb(-1);
//        }
//        reverse(all(trans[i]));
//        cout << " SZ " << sz(trans[i]) << endl;
        if(sz(trans[i]) == 1){
            C[i] = trans[i][0];
        }else{
            C[i] = code(build(trans[i], -1));
        }
    }
    vector<int>X(lst-1-M),Y(lst-1-M);
    for(int f=0;f<sz(X);++f){
        X[f]=code(x[M+1+f]);
        Y[f]=code(y[M+1+f]);
    }
//    cout << "WTF " << sz(X) << ' ' << N << endl;
        assert(sz(X) < 2 * sz(A));
//    cout << "LOL \n";
//    for(int i = 0; i <= M; ++i)
//        cout << C[i] << '\n';
//    for(int f = 0; f < sz(X); ++f){
//        cout << X[f] << ' ' << Y[f] << endl;
//    }
//    cout << endl;
    answer(C,X,Y);
}
/*
4 6
1 2 1 3 1 4
*/

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