Submission #837746

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
837746	2023-08-25 15:27:59	becaido	Mechanical Doll (IOI18_doll)	C++17	100 / 100	90 ms	8736 KiB

doll

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
void create_circuit(int M, vector<int> A) {
    int N, cur = 0;
    vector<int> C(M + 1, -1), X, Y;
    A.emplace_back(0), N = A.size();
    auto rec = [&](auto rec, int sz, int dep)->int {
        cur++;
        int pos = -cur, i = -(pos + 1);
        X.emplace_back(-1), Y.emplace_back(-1);
        if (dep == 0) {
            if (sz == 1) Y[i] = 0;
            if (sz == 2) X[i] = Y[i] = 0;
            return pos;
        }
        int half = 1 << dep;
        if (sz <= half) Y[i] = rec(rec, sz, dep - 1);
        else {
            X[i] = rec(rec, sz - half, dep - 1);
            Y[i] = rec(rec, half, dep - 1);
        }
        return pos;
    };
    rec(rec, N, __lg(N - 1));
    vector<int> b(cur, 0);
    int p = 0, pos = -1;
    while (p < N) {
        int i = -(pos + 1);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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