oj.uz

Submission #1021844

# Submission time Handle Problem Language Result Execution time Memory
1021844 2024-07-13T06:04:23 Z ProtonDecay314 Mechanical Doll (IOI18_doll) C++17
100 / 100
 95 ms 12472 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;
};

// 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);
//         }
//     }
// }

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;
    } /* (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
            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
    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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 29 ms 5280 KB Output is correct
3 Correct 26 ms 4800 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1624 KB Output is correct
6 Correct 41 ms 7180 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 29 ms 5280 KB Output is correct
3 Correct 26 ms 4800 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1624 KB Output is correct
6 Correct 41 ms 7180 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 52 ms 8864 KB Output is correct
9 Correct 54 ms 10308 KB Output is correct
10 Correct 79 ms 12472 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 29 ms 5280 KB Output is correct
3 Correct 26 ms 4800 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1624 KB Output is correct
6 Correct 41 ms 7180 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 52 ms 8864 KB Output is correct
9 Correct 54 ms 10308 KB Output is correct
10 Correct 79 ms 12472 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 80 ms 11452 KB Output is correct
15 Correct 50 ms 7756 KB Output is correct
16 Correct 76 ms 11392 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 78 ms 11616 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 49 ms 8312 KB Output is correct
3 Correct 48 ms 9028 KB Output is correct
4 Correct 72 ms 11432 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 49 ms 8312 KB Output is correct
3 Correct 48 ms 9028 KB Output is correct
4 Correct 72 ms 11432 KB Output is correct
5 Correct 77 ms 11304 KB Output is correct
6 Correct 78 ms 11412 KB Output is correct
7 Correct 78 ms 11196 KB Output is correct
8 Correct 79 ms 11108 KB Output is correct
9 Correct 49 ms 8784 KB Output is correct
10 Correct 76 ms 11404 KB Output is correct
11 Correct 73 ms 11688 KB Output is correct
12 Correct 47 ms 8524 KB Output is correct
13 Correct 53 ms 7492 KB Output is correct
14 Correct 50 ms 7496 KB Output is correct
15 Correct 49 ms 7496 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 47 ms 7380 KB Output is correct
18 Correct 47 ms 7488 KB Output is correct
19 Correct 48 ms 9024 KB Output is correct
20 Correct 79 ms 11200 KB Output is correct
21 Correct 95 ms 11196 KB Output is correct
22 Correct 73 ms 11196 KB Output is correct