oj.uz

Submission #756516

# Submission time Handle Problem Language Result Execution time Memory
756516 2023-06-11T18:51:58 Z drdilyor Mechanical Doll (IOI18_doll) C++17
100 / 100
 672 ms 24464 KB 
#include<bits/stdc++.h>
#include "doll.h"
using namespace std;
using ll = long long;

void create_circuit(int m, std::vector<int> arr) {
    vector<int> c(m+1);
    vector<int> x, y;
    auto add = [&](int a, int b){
        x.push_back(a), y.push_back(b);
        return -(int)x.size();
    };

    auto tree = [&](auto& tree, vector<int> nxt) {
        //cout << "nxt="; for (int i : nxt) cout << (i == INT_MAX ? -1 : i) << ' '; cout << endl;
        if (set<int>(nxt.begin(), nxt.end()).size() == 1) {
            return nxt[0];
        }
        vector<int> odd, even;
        for (int i = 0; i < (int)nxt.size(); i += 2) {
            odd.push_back(nxt[i]);
            even.push_back(nxt[i+1]);
        }
        int t1 = tree(tree, odd);
        int t2 = tree(tree, even);
        return add(t1, t2);
    };


    arr.push_back(0);

    int k = arr.size();
    while (k & (k-1)) k++;
    vector<int> order(k), rev(k);
    for (int i = 0; i < k; i++) {
        for (int j = 0; (1<<j) < k; j++) {
            if (i & (1<<j))
                order[i] |= k >> (j+1);
        }
        rev[order[i]] = i;
    }

    vector<int> brr(k, INT_MAX);

    set<int> available(order.begin() + k - arr.size(), order.end());
    int cur = 0;
    for (int i : available)
        brr[i] = arr[cur++];

    c[0] = tree(tree, brr);

    for (int i = 0; i < (int)x.size(); i++) {
        if (x[i] == INT_MAX)
            x[i] = c[0];
        if (y[i] == INT_MAX)
            y[i] = c[0];
    }
    for (int i = 1; i <= m; i++)
        c[i] = c[0];
    answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 200 ms 10156 KB Output is correct
3 Correct 200 ms 10524 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 13 ms 1452 KB Output is correct
6 Correct 300 ms 13636 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 200 ms 10156 KB Output is correct
3 Correct 200 ms 10524 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 13 ms 1452 KB Output is correct
6 Correct 300 ms 13636 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 424 ms 19480 KB Output is correct
9 Correct 445 ms 20120 KB Output is correct
10 Correct 672 ms 24464 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 200 ms 10156 KB Output is correct
3 Correct 200 ms 10524 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 13 ms 1452 KB Output is correct
6 Correct 300 ms 13636 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 424 ms 19480 KB Output is correct
9 Correct 445 ms 20120 KB Output is correct
10 Correct 672 ms 24464 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 654 ms 23416 KB Output is correct
15 Correct 385 ms 18416 KB Output is correct
16 Correct 622 ms 23156 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 637 ms 23992 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 75 ms 14636 KB Output is correct
3 Correct 69 ms 14660 KB Output is correct
4 Correct 130 ms 18368 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 75 ms 14636 KB Output is correct
3 Correct 69 ms 14660 KB Output is correct
4 Correct 130 ms 18368 KB Output is correct
5 Correct 614 ms 21732 KB Output is correct
6 Correct 578 ms 21480 KB Output is correct
7 Correct 579 ms 21788 KB Output is correct
8 Correct 539 ms 21708 KB Output is correct
9 Correct 150 ms 16392 KB Output is correct
10 Correct 390 ms 21124 KB Output is correct
11 Correct 415 ms 21620 KB Output is correct
12 Correct 257 ms 16584 KB Output is correct
13 Correct 350 ms 17356 KB Output is correct
14 Correct 373 ms 16820 KB Output is correct
15 Correct 373 ms 17588 KB Output is correct
16 Correct 8 ms 724 KB Output is correct
17 Correct 274 ms 14400 KB Output is correct
18 Correct 256 ms 16704 KB Output is correct
19 Correct 266 ms 16620 KB Output is correct
20 Correct 484 ms 21780 KB Output is correct
21 Correct 386 ms 20892 KB Output is correct
22 Correct 444 ms 21856 KB Output is correct