제출 #1021847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1021847		ProtonDecay314	Mechanical Doll (IOI18_doll)	C++17	100 / 100	85 ms	12236 KiB

doll

// AM+DG

/*

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
#define L(i, varmn, varmx) for(ll i = varmn; i < varmx; i++)
#define LR(i, varmx, varmn) for(ll i = varmx; i > varmn; i--)
#define LI(i, varmn, varmx) for(int i = varmn; i < varmx; i++)
#define LIR(i, varmx, varmn) for(int i = varmx; i > varmn; i--)
#define pb push_back
#include "doll.h"

struct pot_switch {
    int id;
    int x;
    int y;
};

const int TO_PROCESS_OFFSETTER = 1000000;

int construct_switches(int cur_switch_num, int num_to_remove, int p2, int offset, int size, vector<pot_switch>& switches_to_construct) {
    if(size == 2) {
        // Handle the special case here
        // ! Oh btw, I added "TO_PROCESS_OFFSETTER" to indicate that the switch exit still needs to be processed, haha
        // ! Otherwise, the algorithm might relabel some of the already processed exits and cause wrong motion, haha
        if(num_to_remove == 1) {
            switches_to_construct.pb({cur_switch_num, -1, TO_PROCESS_OFFSETTER + (p2 << 1) + offset - ((p2 << 1) - 1)});
        } else {
            switches_to_construct.pb({cur_switch_num, TO_PROCESS_OFFSETTER + p2 + offset - ((p2 << 1) - 1), TO_PROCESS_OFFSETTER + (p2 << 1) + offset - ((p2 << 1) - 1)});
        }
        return cur_switch_num - 1;
    } else {
        if(num_to_remove < (size >> 1)) {
            // Recursive case
            pot_switch sw = {cur_switch_num, cur_switch_num - 1, -1};

            // Recurse left
            int next_switch_num = construct_switches(cur_switch_num - 1, num_to_remove, p2 << 1, offset + p2, size >> 1, switches_to_construct);
            sw.y = next_switch_num;

            // Recurse right
            next_switch_num = construct_switches(next_switch_num, 0, p2 << 1, offset + (p2 << 1), size >> 1, switches_to_construct);
            switches_to_construct.pb(sw);

            return next_switch_num;
        } else {
            // Recursive case
            pot_switch sw = {cur_switch_num, -1, cur_switch_num - 1};

            // Recurse right
            int next_switch = construct_switches(cur_switch_num - 1, num_to_remove - (size >> 1), p2 << 1, offset + (p2 << 1), size >> 1, switches_to_construct);
            
            switches_to_construct.pb(sw);
            
            return next_switch;
        }
    }
}

int ceillog2(int n) {
    int p2 = 1;

    while(p2 < n) {
        p2 <<= 1;
    }

    return p2;
}

void create_circuit(int m, std::vector<int> a) {
    a.pb(0); // Zero ni natte.. zero ni natte.. /ref (see https://music.youtube.com/watch?v=ZEy36W1xX8c)
    int n = a.size();
    vi c(m + 1);
    for (int i = 0; i <= m; ++i) {
        c[i] = -1;
    }

    vi x;
    vi y;
    

    int actual_size = ceillog2(n);
    int to_remove = actual_size - n;

    vector<pot_switch> switches_to_construct;
    construct_switches(-1, to_remove, 1, 0, actual_size, switches_to_construct);

    priority_queue<pi, vector<pi>, greater<pi>> exits_to_renumber;


    int num_switches = switches_to_construct.size();

    LI(i, 0, num_switches) {
        pot_switch sw = switches_to_construct[i];
        if(sw.x >= 0) {
            exits_to_renumber.push({sw.x, i});
        }
        if(sw.y >= 0) {
            exits_to_renumber.push({sw.y, i});
        }
    }

    int ptr = 0;
    while(!exits_to_renumber.empty()) {
        pi top_elem = exits_to_renumber.top();
        int num = top_elem.first, i = top_elem.second;
        exits_to_renumber.pop();

        if(switches_to_construct[i].x == num) {
            switches_to_construct[i].x = a[ptr];
        } else {
            switches_to_construct[i].y = a[ptr];
        }

        ptr++;
    }

    sort(switches_to_construct.begin(), switches_to_construct.end(), [](pot_switch s1, pot_switch s2){return s1.id > s2.id;});

    LI(i, 0, (int)switches_to_construct.size()) {
        // cout << switches_to_construct[i].id << " " << switches_to_construct[i].x << " " << switches_to_construct[i].y << endl;
        x.pb(switches_to_construct[i].x);
        y.pb(switches_to_construct[i].y);
    }

    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