Submission #1162753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162753		PagodePaiva	Mechanical Doll (IOI18_doll)	C++17	6 / 100	71 ms	16552 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;

void solve(int valor){
    if(cnt[valor].empty()) {
        c.push_back(valor);
        return;
    }
    queue <pair <vector <int>, int>> ans;
    for(auto v : cnt[valor]){
        ans.push({{v}, v});
    }
    int cnt = 1;
    while(cnt < ans.size()){
        cnt *= 2;
    }
    while(ans.size() < cnt){
        ans.push({{M}, valor});
    }
    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{
            x.push_back(rep);
            y.push_back(rep2);
            ans.push({nv, at});
            at--;
        }
    }
    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);
    }
    answer(c, x, y);
    return;
}

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