Submission #659629

#	Time	Username	Problem	Language	Result	Execution time	Memory
659629		urosk	Mechanical Doll (IOI18_doll)	C++14	100 / 100	145 ms	15204 KiB

doll

#include "doll.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll int
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
using namespace __gnu_pbds;
#define maxn 400005
ll n,m;
ll a[maxn];
ll pos[maxn],ls[maxn],rs[maxn];
ll it = 0,k,rut;
vector<ll> reshi(vector<ll> v){
    if(sz(v)<=1) return v;
    vector<vector<ll> > u(2);
    for(ll i = 0;i<sz(v);i++) u[i&1].pb(v[i]);
    u[0] = reshi(u[0]); u[1] = reshi(u[1]);
    v.clear();
    for(ll x : u[0]) v.pb(x);
    for(ll x : u[1]) v.pb(x);
    return v;
}
void reshi(ll &v,ll tl,ll tr){
    if(tr<=k){v = rut;return;}
    if(tl==tr){v = -a[tl];return;}
    v = ++it;
    ll mid = (tl+tr)/2;
    reshi(ls[v],tl,mid);
    reshi(rs[v],mid+1,tr);
}
void create_circuit(int M, vector<int> A) {
    A.pb(0);
    n = sz(A); m = M;
    ll d = 1;
    while(d<n) d*=2;
    vector<ll> v(d); iota(all(v),1);
    v = reshi(v);
    k = d-n;
    for(ll i = k;i<d;i++) pos[v[i]] = i+1;
    for(ll i = 1,j = 0;i<=d;i++){
        if(pos[i]){
            a[pos[i]] = A[j]; j++;
        }
    }
    reshi(rut,1,d);
    vector<ll> C(m+1,-1),X,Y;
    for(ll i = 1;i<=it;i++) X.pb(-ls[i]),Y.pb(-rs[i]);
    answer(C,X,Y);
}
/*
4 4
1 2 1 3
*/

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