Submission #1186633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186633		HappyCapybara	자동 인형 (IOI18_doll)	C++17	100 / 100	62 ms	17588 KiB

doll

#include<bits/stdc++.h>
#include "doll.h"
using namespace std;

void create_circuit(int m, vector<int> a){
    int bruh = a[0];
    int n = a.size();
    int pn;
    if (n == 1) pn = 2;
    else pn = pow(2, floor(log2(n-1))+1);
    vector<int> b;
    for (int i=1; i<n; i++) b.push_back(a[i]);
    b.push_back(0);
    vector<int> v = {0}, w;
    while (v.size() != pn){
        w = {};
        swap(v, w);
        for (int x : w){
            v.push_back(x);
            v.push_back(x + (int) w.size());
        }
    }
    vector<pair<int,int>> fts;
    for (int i=pn-n; i<pn; i++) fts.push_back({v[i], i});
    sort(fts.begin(), fts.end());
    a.assign(pn, -1);
    for (int i=0; i<n; i++) a[fts[i].first] = b[i];
    //for (int x : a) cout << x << " ";
    //cout << endl;
    vector<int> c(m+1, -1), x(pn-1, -1), y(pn-1, -1);
    c[0] = bruh;
    for (int i=0; i<pn-1; i++){
        if (2*(i+1) < pn-1){
            x[i] = -2*(i+1);
            y[i] = -2*(i+1)-1;
        }
        else {
            x[i] = a[v[2*(i+1)-pn]];
            y[i] = a[v[2*(i+1)+1-pn]];
        }
    }
    unordered_set<int> del;
    for (int i=pn-2; i>=1; i--){
        if ((x[i] == -1 && y[i] == -1) || (del.find(-x[i]-1) != del.end() && del.find(-y[i]-1) != del.end())) del.insert(i);
    }
    vector<int> ns(pn-1, -1);
    int cs = 0;
    for (int i=0; i<pn-1; i++){
        if (del.find(i) == del.end()){
            ns[i] = cs;
            cs++;
        }
    }
    vector<int> nx(cs), ny(cs);
    for (int i=0; i<pn-1; i++){
        if (ns[i] == -1) continue;
        nx[ns[i]] = x[i];
        if (x[i] < 0){
            nx[ns[i]] = -ns[-x[i]-1]-1;
            if (nx[ns[i]] == 0) nx[ns[i]] = -1;
        }
        ny[ns[i]] = y[i];
        if (y[i] < 0){
            ny[ns[i]] = -ns[-y[i]-1]-1;
            if (ny[ns[i]] == 0) ny[ns[i]] = -1;
        }
    }
    answer(c, nx, ny);
}

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