Submission #1162758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162758		PagodePaiva	Mechanical Doll (IOI18_doll)	C++17	24 / 100	96 ms	25184 KiB

doll

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

using namespace std;

const int M = 200010;

vector <int> cnt[M];
int at = -1;
vector <int> c, x, y;

vector <int> order(vector <int> v){
    int cnt = 1;
    while(cnt < v.size()){
        cnt *= 2;
    }
    if(cnt == 1) return v;
    int add = cnt-v.size();
    vector <int> vv[2];
    while(add > 0){
        vv[add%2].push_back(M);
        add--;
    }
    reverse(v.begin(), v.end());
    while(vv[0].size() < cnt/2){
        vv[0].push_back(v.back());
        v.pop_back();
    }
    while(vv[1].size() < cnt/2){
        vv[1].push_back(v.back());
        v.pop_back();
    }
    v = vv[0];
    for(auto x : vv[1])
        v.push_back(x);
    return v;
}

void solve(int valor){
    if(cnt[valor].empty()) {
        c.push_back(valor);
        return;
    }
    vector <int> aux = order(cnt[valor]);
    queue <pair <vector <int>, int>> ans;
    for(auto v : aux){
        ans.push({{v}, v});
        //cout << v << ' ';
    }
    //cout << '\n';
    vector <pair <int, int>> novos;
    while(ans.size() > 1){
        auto [a, rep] = ans.front();
        ans.pop();
        auto [b, rep2] = ans.front();
        ans.pop();
        vector <int> nv;
        for(int i = 0;i < a.size();i++){
            nv.push_back(a[i]);
            nv.push_back(b[i]);
        }
        if(rep == rep2){
            ans.push({nv, rep});
        }
        else{
            novos.push_back({rep, rep2});
            ans.push({nv, at});
            at--;
        }
    }
    for(auto [a, b] : novos){
        if(a == M) a = ans.back().second;
        if(b == M) b = ans.back().second;
        x.push_back(a);
        y.push_back(b);
    }
    c.push_back(ans.back().second);
}

void create_circuit(int m, std::vector<int> A) {
    int n = A.size();
    A.push_back(0);
    cnt[0].push_back(A[0]);
    for(int i = 0;i < n;i++){
        cnt[A[i]].push_back(A[i+1]);
    }
    for(int i = 0;i <= m;i++){
        solve(i);
    }
    /*for(auto x : c){
        cout << x << ' ';
    }
    cout << '\n';
    for(int i = 0;i < x.size();i++){
        cout << x[i] << ' ' << y[i] << '\n';
    }*/
    answer(c, x, y);
    return;
}

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