Submission #611800

#	Time	Username	Problem	Language	Result	Execution time	Memory
611800		rrrr10000	Mechanical Doll (IOI18_doll)	C++14	100 / 100	402 ms	54132 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> P;
typedef vector<vi> vvi;
typedef vector<P> vp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
const ll inf=1001001001001001;
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}

void create_circuit(int M, vector<int> A) {
    ll n=A.size();
    vi v;
    v.pb(0);
    for(int i=n-1;i>0;i--)v.pb(A[i]);
    vector<pair<vi,ll>> ord;
    rep(i,v.size()){
        vi al;
        rep(j,19)al.pb(i>>j&1);
        ord.pb(al,i);
    }
    sort(all(ord));
    vi tmp(ord.size());
    rep(i,ord.size())tmp[ord[i].se]=v[i];
    vp res;
    ll cnt=0;
    while(tmp.size()>1){
        vi ntmp;
        rep(j,tmp.size()/2){
            ntmp.pb(--cnt);
            res.pb(tmp[j*2+1],tmp[j*2]);
        }
        if(tmp.size()%2){
            ntmp.pb(--cnt);
            res.pb(inf,tmp.back());
        }
        tmp=ntmp;
    }
    vector<int> C(M+1,tmp[0]);
    C[0]=A[0];
    rep(i,res.size())if(res[i].fi==inf)res[i].fi=tmp[0];
    vector<int> X,Y;
    for(auto x:res){
        X.pb(x.fi);Y.pb(x.se);
    }
    answer(C,X,Y);
}

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