Submission #1123741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123741		Pacybwoah	Mechanical Doll (IOI18_doll)	C++20	11 / 100	80 ms	14112 KiB

doll

#include "doll.h"
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
namespace{
    int n, m;
    int cnt = 1;
    vector<int> c, x, y;
    vector<int> bot;
    void build(int dep, int fin){
        int id = cnt;
        if(dep < fin){
            cnt++;
            x[id - 1] = -cnt;
            build(dep + 1, fin);
            cnt++;
            y[id - 1] = -cnt;
            build(dep + 1, fin);
        }
        else{
            bot.push_back(cnt);
        }
    }
}

void create_circuit(int M, std::vector<int> A){
    m = M;
    n = A.size();
    c.resize(m + 1);
    x.resize(3 * n + 1);
    y.resize(3 * n + 1);
    fill(x.begin(), x.end(), 12345678);
    fill(y.begin(), y.end(), 12345678);
    A.push_back(0);
    c[0] = A[0];
    vector<vector<int>> nxt(m + 1);
    for(int i = 0; i < n; i++){
        nxt[A[i]].push_back(A[i + 1]);
    }
    for(int i = 1; i <= m; i++){
        int sz = (int)nxt[i].size();
        if(sz == 0) continue;
        if(sz == 1){
            c[i] = nxt[i][0];
            continue;
        }
        int dep = 0;
        while((1 << dep) < sz) dep++;
        c[i] = -cnt;
        int hi = cnt;
        vector<int>().swap(bot);
        build(1, dep);
        vector<pair<int, int>> bott;
        int cntt = 0;
        for(auto &x: bot){
            int now = 0, ori = cntt;
            while(cntt > 0){
                now *= 2;
                now += cntt % 2;
                cntt /= 2;
            }
            bott.emplace_back(x, now);
            cntt = ori;
            cntt++;
        }
        auto cmp = [&](pair<int, int> a, pair<int, int> b){
            return a.second < b.second;
        };
        int szz = bot.size();
        for(int j = 0; j < szz; j++) bot[j] = bott[j].first;
        for(int j = 0; j < (1 << dep) - sz; j++){
            if(j & 1) y[bot[j / 2] - 1] = -hi;
            else x[bot[j / 2] - 1] = -hi;
        }
        for(int j = (1 << dep) - sz; j < (1 << dep); j++){
            if(j & 1) y[bot[j / 2] - 1] = nxt[i][j - (1 << dep) + sz];
            else x[bot[j / 2] - 1] = nxt[i][j - (1 << dep) + sz];
        }
    }
    while(!x.empty() && x.back() == 12345678) x.pop_back();
    while(!y.empty() && y.back() == 12345678) y.pop_back();
    answer(c, x, y);
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run grader.cpp doll.cpp

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