Submission #824119

#	Time	Username	Problem	Language	Result	Execution time	Memory
824119		ALeonidou	Mechanical Doll (IOI18_doll)	C++17	100 / 100	92 ms	14384 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007
#define INF 1e18
#define ll int
typedef vector <ll> vi;
typedef pair <ll,ll> ii;
typedef vector <ii> vii;
#define F first
#define S second
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;
#define dbg4(x,y,z,w) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<" "<<#w<<": "<<w<<endl;
#define sz(x) (ll)x.size()
#define pb push_back
#define MID ((l+r)/2)

void printVct(vi &v){
    for (ll i= 0; i<sz(v); i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

void printVct2D(vector <vi> &adj){
    for (ll i =0; i<sz(adj); i++){
        cout<<i<<": ";
        for (ll j =0; j<sz(adj[i]); i++){
            cout<<adj[i][j]<<" ";
        }
        cout<<endl;
    }
}

void printVctPair(vector <ii> &v){
    for (ll i= 0; i<sz(v); i++){
        cout<<"("<<v[i].F<<","<<v[i].S<<"),";
    }
}

vi mp;
void calcLeafVal(ll treeSize){  //treeSize = # leafs
    vi cur, tmp;
    cur.pb(1);

    while (sz(cur) < treeSize){     //O(logn)
        tmp.resize(sz(cur) * 2);
        for (ll i = 0; i<sz(cur); i++){     //O(n)
            tmp[i*2] = cur[i];
            tmp[i*2+1] = tmp[i*2] + sz(cur);
        }
        cur = tmp;
        // cout<<"cur: ";
        // printVct(cur);
    }
    mp = cur;
}

vi c, x, y;
vi arr;
ll treeSize;   // e.g. 16
ll targetComb;
ll curComb = 0;   //perfect tree size
ll cnt = 0;
ll cntLeafs = 0;

void binaryTree(ll l = 1, ll r = treeSize){
    //dbg4(l,r, cnt, cntLeafs);
    x.pb(0), y.pb(0);
    ll cntCur = cnt;
    cnt++;
    
    ll val = (r - l + 1) * 2;
    ll nextVal = val/2;

    if (curComb - nextVal >= targetComb){
        //ignore down left
        x[cntCur] = -1;
        curComb -= nextVal;
    }
    else{
        if (l == r){
            x[cntCur] = arr[mp[cntLeafs]];
            cntLeafs ++; 
        }
        else{
            x[cntCur] = (cnt + 1) * -1;
            binaryTree(l, MID);
        }
    }

    if (l == r){
        y[cntCur] = arr[mp[cntLeafs]];
        cntLeafs ++; 
    }
    else{
        y[cntCur] = (cnt + 1) * -1;
        binaryTree (MID+1, r);
    }

}

void create_circuit(int m, vi v) {


    bool complicated = false;

    ll n = sz(v);
    vi tmp = v;
    sort(tmp.begin(), tmp.end());
    for (ll i=1; i<n; i++){
        if (tmp[i] == tmp[i-1]){
            complicated = true;
            break;
        }
    }

    //dbg(complicated);
    if (!complicated){
        c.assign(m+1, 0);
        ll a,b;
        c[0] = v[0];
        for(ll i=0; i<n; i++){
            a = v[i];
            if (i<n-1) b = v[i+1]; else b = 0;
            c[a] = b;
        }  
    }
    else{  
        v.pb(0);
        targetComb = sz(v);
        c.assign(m+1, -1);
        arr = v;

        curComb = 1;
        while (curComb < targetComb) curComb *= 2;
        treeSize = curComb / 2;

        //dbg3(curComb, targetComb, treeSize);

        calcLeafVal(curComb);

        // cout<<"mp: "<<endl;
        // printVct(mp);

        vii com;
        ll dif = curComb - targetComb;
        for(ll i =dif; i<sz(mp) ;i++){
            com.pb(ii(mp[i], i));
        }
        //printVctPair(com);
        
        sort (com.begin(), com.end());
        tmp.assign(curComb,-1);
        for (ll i =0; i<sz(com); i++){
            tmp[com[i].S] = i;
        }
        mp.clear();
        for (ll i =0; i<sz(tmp); i++){
            if (tmp[i] != -1){
                mp.pb(tmp[i]);
            }
        }

        // cout<<"mp: "<<endl;
        // printVct(mp);
        
        binaryTree();
    }

    // printVct(c);
    // printVct(x);
    // printVct(y);
    answer(c,x,y);
}

/*
5 10
1 2 1 3 4 1 2 2 1 4

4 4
1 2 1 3

4 4
1 2 3 4

6 4
2 4 3 1

1 1
1

6 6 
6 5 1 2 4 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