oj.uz

Submission #330483

# Submission time Handle Problem Language Result Execution time Memory
330483 2020-11-25T13:53:34 Z aquablitz11 Mechanical Doll (IOI18_doll) C++14
100 / 100
 139 ms 9936 KB 
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;

const int INF = 2e9;

vector<int> C, X, Y;
int cnt = 0;

int get_switch(int x, int y) {
    X.push_back(x);
    Y.push_back(y);
    return --cnt;
}

int create_tree(const vector<int> &v) {
    bool ok = true;
    for (int i = 0; i < (int)v.size()-1; ++i) {
        if (v[i] != v[i+1])
            ok = false;
    }
    if (ok)
        return v[0];
    vector<int> vx, vy;
    for (int i = 0; i < v.size(); ++i) {
        if (i % 2 == 0)
            vx.push_back(v[i]);
        else
            vy.push_back(v[i]);
    }
    int x = create_tree(vx);
    int y = create_tree(vy);
    return get_switch(x, y);
}

int reverse_bit(int k, int a) {
    int b = 0;
    while (k--) {
        b <<= 1;
        b |= (a&1);
        a >>= 1;
    }
    return b;
}

void create_circuit(int M, vector<int> A) {

    // find k
    int n = A.size();
    int k = 0;
    while ((1<<k) < n)
        ++k;

    vector<int> v(1<<k, 0);
    for (int i = 0; i < (1<<k)-n; ++i)
        v[reverse_bit(k, i)] = INF;

    int cnt = 0;
    for (int i = 1; i < n; ++i) {
        while (cnt < v.size() && v[cnt] != 0) ++cnt;
        v[cnt] = A[i];
    }

    n = 1<<k;
    v[n-1] = 0;
    int r = create_tree(v);
    C = vector<int>(M+1, r);
    C[0] = A[0];
    for (auto &x: X) {
        if (x == INF)
            x = r;
    }
    for (auto &y: Y) {
        if (y == INF)
            y = r;
    }
    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'int create_tree(const std::vector<int>&)':
doll.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int i = 0; i < v.size(); ++i) {
      |                     ~~^~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         while (cnt < v.size() && v[cnt] != 0) ++cnt;
      |                ~~~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 52 ms 4476 KB Output is correct
3 Correct 47 ms 4364 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1476 KB Output is correct
6 Correct 69 ms 5616 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 52 ms 4476 KB Output is correct
3 Correct 47 ms 4364 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1476 KB Output is correct
6 Correct 69 ms 5616 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 82 ms 6088 KB Output is correct
9 Correct 95 ms 8144 KB Output is correct
10 Correct 132 ms 9936 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 52 ms 4476 KB Output is correct
3 Correct 47 ms 4364 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1476 KB Output is correct
6 Correct 69 ms 5616 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 82 ms 6088 KB Output is correct
9 Correct 95 ms 8144 KB Output is correct
10 Correct 132 ms 9936 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 129 ms 9268 KB Output is correct
15 Correct 82 ms 6248 KB Output is correct
16 Correct 124 ms 9396 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 2 ms 288 KB Output is correct
20 Correct 139 ms 9340 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 19 ms 2856 KB Output is correct
3 Correct 25 ms 4368 KB Output is correct
4 Correct 40 ms 4908 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 19 ms 2856 KB Output is correct
3 Correct 25 ms 4368 KB Output is correct
4 Correct 40 ms 4908 KB Output is correct
5 Correct 133 ms 9228 KB Output is correct
6 Correct 116 ms 8856 KB Output is correct
7 Correct 118 ms 8940 KB Output is correct
8 Correct 118 ms 8716 KB Output is correct
9 Correct 69 ms 5720 KB Output is correct
10 Correct 113 ms 7824 KB Output is correct
11 Correct 112 ms 8324 KB Output is correct
12 Correct 81 ms 6072 KB Output is correct
13 Correct 75 ms 5792 KB Output is correct
14 Correct 83 ms 6092 KB Output is correct
15 Correct 88 ms 6236 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 72 ms 5812 KB Output is correct
18 Correct 74 ms 5852 KB Output is correct
19 Correct 81 ms 6112 KB Output is correct
20 Correct 127 ms 8524 KB Output is correct
21 Correct 113 ms 8324 KB Output is correct
22 Correct 117 ms 8312 KB Output is correct