Submission #1162789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162789		PagodePaiva	Mechanical Doll (IOI18_doll)	C++17	100 / 100	281 ms	30248 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;
int m;

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();
    int aaad = add;
    reverse(v.begin(), v.end());
    while(add > 0){
        v.push_back(M);
        add--;
    }    
    reverse(v.begin(), v.end());
    vector <int> aux;
    for(int i = 0;i < v.size();i++){
        aux.push_back(i);
    }
    vector <int> answer;
    stack <vector <int>> q;
    q.push(aux);
    while(!q.empty()){
        auto vv = q.top();
        q.pop();
        if(vv.size() == 1){
            answer.push_back(vv.back());
        }
        else{
            vector <int> v1, v2;
            for(int i = 0;i < vv.size();i++){
                if(i%2 == 0) v1.push_back(vv[i]);
                else v2.push_back(vv[i]);
            }
            q.push(v2);
            q.push(v1);
        }
    }
    map <int, int> comp;
    vector <int> aa;
    for(int i = 0;i < v.size();i++){
        if(v[i] == M) continue;
        aa.push_back(answer[i]);
    }
    sort(aa.begin(), aa.end());
    for(int i = 0;i < aa.size();i++){
        // cout << aa[i] << ' ';
        comp[aa[i]] = i+aaad;
    }
    // cout << '\n';
    for(int i = 0;i < aa.size();i++){
        answer[i+aaad] = comp[answer[i+aaad]];
    }
    vector <int> resposta;
    while(resposta.size() < aaad){
        resposta.push_back(M);
    }
    for(int i = 0;i < aa.size();i++){
        resposta.push_back(v[answer[i+aaad]]);
    }
    return resposta;
}

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);
    }
    for(int i = 0;i <= m;i++){
        c.push_back(ans.back().second);
    }
}

void create_circuit(int mm, std::vector<int> A) {
    int n = A.size();
    m = mm;
    A.push_back(0);
    cnt[0].push_back(A[0]);
    for(int i = 0;i < n;i++){
        cnt[0].push_back(A[i+1]);
    }
    solve(0);
    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: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56