제출 #1021767

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1021767		ProtonDecay314	Mechanical Doll (IOI18_doll)	C++17	0 / 100	1 ms	348 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;
};

void construct_switches(int base_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
        if(num_to_remove == 1) {
            switches_to_construct.pb({base_switch_num - offset, -1, (p2 << 1) + offset - ((p2 << 1) - 1)});
        } else {
            switches_to_construct.pb({base_switch_num - offset, p2 + offset - ((p2 << 1) - 1), (p2 << 1) + offset - ((p2 << 1) - 1)});
        }
    } /* (No need for this, we're making a perfect binary tree anyways) else if(size == 3) {
        // Handle the special case here
        if(num_to_remove == 2) {
            switches_to_construct.pb({base_switch_num - offset, -1, (p2 << 1) + offset - ((p2 << 1) - 1)});
        } else {
            switches_to_construct.pb({base_switch_num - offset, base_switch_num - (offset + p2), (p2 << 1) + offset - ((p2 << 1) - 1)});

            // Recurse towards the first child
            construct_switches(base_switch_num, num_to_remove, p2 << 1, offset + p2, size - (size >> 1), switches_to_construct);
        }
    }*/ else {
        if(num_to_remove < (size >> 1)) {
            // Recursive case
            switches_to_construct.pb({base_switch_num - offset, base_switch_num - (offset + p2), base_switch_num - (offset + (p2 << 1))});

            // Recurse left
            construct_switches(base_switch_num, num_to_remove, p2 << 1, offset + p2, size >> 1, switches_to_construct);

            // Recurse right
            construct_switches(base_switch_num, 0, p2 << 1, offset + (p2 << 1), size >> 1, switches_to_construct);
        } else {
            // Recursive case
            switches_to_construct.pb({base_switch_num - offset, -1, base_switch_num - (offset + (p2 << 1))});

            // Recurse right
            construct_switches(base_switch_num, num_to_remove - (size >> 1), p2 << 1, offset + (p2 << 1), size >> 1, switches_to_construct);
        }
    }
}

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
    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>> switches_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) {
            switches_to_renumber.push({sw.x, i});
        }
        if(sw.y >= 0) {
            switches_to_renumber.push({sw.y, i});
        }
    }

    int ptr = 0;
    while(!switches_to_renumber.empty()) {
        pi top_elem = switches_to_renumber.top();
        int num = top_elem.first, i = top_elem.second;
        switches_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++;
    }

    assert(ptr == n);

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

    LI(i, 0, n + 1) {
        x.pb(switches_to_construct[i].x);
        y.pb(switches_to_construct[i].y);
    }

    answer(c, x, y);

    return;
}

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