oj.uz

답안 #1021847

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1021847 2024-07-13T06:07:07 Z ProtonDecay314 자동 인형 (IOI18_doll) C++17
100 / 100
 85 ms 12236 KB 
// 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.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 30 ms 5324 KB Output is correct
3 Correct 28 ms 4812 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 42 ms 7084 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 30 ms 5324 KB Output is correct
3 Correct 28 ms 4812 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 42 ms 7084 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 53 ms 9032 KB Output is correct
9 Correct 57 ms 8800 KB Output is correct
10 Correct 85 ms 12216 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 30 ms 5324 KB Output is correct
3 Correct 28 ms 4812 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 42 ms 7084 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 53 ms 9032 KB Output is correct
9 Correct 57 ms 8800 KB Output is correct
10 Correct 85 ms 12216 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 81 ms 11772 KB Output is correct
15 Correct 53 ms 9032 KB Output is correct
16 Correct 82 ms 11192 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 82 ms 12236 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 51 ms 7644 KB Output is correct
3 Correct 49 ms 7496 KB Output is correct
4 Correct 76 ms 11192 KB Output is correct

Subtask #6
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 51 ms 7644 KB Output is correct
3 Correct 49 ms 7496 KB Output is correct
4 Correct 76 ms 11192 KB Output is correct
5 Correct 79 ms 11196 KB Output is correct
6 Correct 79 ms 11708 KB Output is correct
7 Correct 81 ms 11196 KB Output is correct
8 Correct 80 ms 11192 KB Output is correct
9 Correct 55 ms 7492 KB Output is correct
10 Correct 76 ms 11056 KB Output is correct
11 Correct 77 ms 11104 KB Output is correct
12 Correct 50 ms 7488 KB Output is correct
13 Correct 50 ms 7500 KB Output is correct
14 Correct 53 ms 7592 KB Output is correct
15 Correct 51 ms 7480 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 50 ms 7356 KB Output is correct
18 Correct 50 ms 7596 KB Output is correct
19 Correct 50 ms 7492 KB Output is correct
20 Correct 79 ms 11200 KB Output is correct
21 Correct 85 ms 11232 KB Output is correct
22 Correct 77 ms 11196 KB Output is correct