oj.uz

Submission #107348

# Submission time Handle Problem Language Result Execution time Memory
107348 2019-04-23T12:13:16 Z PeppaPig Mechanical Doll (IOI18_doll) C++14
100 / 100
 172 ms 10472 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+5;
const int INF = 1e9+1;

int n, m, ptr;
vector<int> C, X, Y;

int solve(vector<int> &V) {
    if((int)V.size() == 1 || (V[0] == -INF && V.back() == -INF)) return V[0];
    vector<int> L, R;
    for(int i = 0; i < (int)V.size(); i++) {
        if(i & 1) R.emplace_back(V[i]);
        else L.emplace_back(V[i]);
    }
    int l = solve(L), r = solve(R);
    X.emplace_back(l), Y.emplace_back(r);
    return --ptr;
}

void create_circuit(int M, vector<int> A) {
    A.emplace_back(0);
    n = A.size(), m = M;
    
    int L = 0, sz;
    while((1 << L) < (int)A.size()) ++L;
    sz = 1 << L;

    vector<int> V;
    for(int i = 0; i < sz; i++) {
        int pos = 0;
        for(int j = 0; j < L; j++) pos += (i >> j & 1) << (L - j - 1);
        V.emplace_back(pos >= sz - n); 
    }
    for(int i = 0, idx = 0; i < sz; i++) {
        if(V[i]) V[i] = A[idx++];
        else V[i] = -INF;
    }

    int root = solve(V);

    C = vector<int>(m+1, root);
    for(int &v : X) if(v == -INF) v = root;
    for(int &v : Y) if(v == -INF) v = root;

    answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 50 ms 4708 KB Output is correct
3 Correct 48 ms 4368 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1388 KB Output is correct
6 Correct 70 ms 6532 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 50 ms 4708 KB Output is correct
3 Correct 48 ms 4368 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1388 KB Output is correct
6 Correct 70 ms 6532 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 97 ms 7512 KB Output is correct
9 Correct 93 ms 8264 KB Output is correct
10 Correct 172 ms 10472 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 50 ms 4708 KB Output is correct
3 Correct 48 ms 4368 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1388 KB Output is correct
6 Correct 70 ms 6532 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 97 ms 7512 KB Output is correct
9 Correct 93 ms 8264 KB Output is correct
10 Correct 172 ms 10472 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 133 ms 9900 KB Output is correct
15 Correct 90 ms 6860 KB Output is correct
16 Correct 121 ms 9456 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 136 ms 10120 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 2 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 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 204 KB Output is correct
2 Correct 79 ms 6692 KB Output is correct
3 Correct 78 ms 6724 KB Output is correct
4 Correct 112 ms 8080 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 79 ms 6692 KB Output is correct
3 Correct 78 ms 6724 KB Output is correct
4 Correct 112 ms 8080 KB Output is correct
5 Correct 131 ms 9224 KB Output is correct
6 Correct 118 ms 8980 KB Output is correct
7 Correct 128 ms 9108 KB Output is correct
8 Correct 129 ms 8860 KB Output is correct
9 Correct 83 ms 6720 KB Output is correct
10 Correct 123 ms 8792 KB Output is correct
11 Correct 135 ms 8484 KB Output is correct
12 Correct 80 ms 6716 KB Output is correct
13 Correct 93 ms 6704 KB Output is correct
14 Correct 82 ms 6788 KB Output is correct
15 Correct 105 ms 6788 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 80 ms 7072 KB Output is correct
18 Correct 77 ms 6696 KB Output is correct
19 Correct 84 ms 6720 KB Output is correct
20 Correct 117 ms 8608 KB Output is correct
21 Correct 164 ms 8480 KB Output is correct
22 Correct 149 ms 8604 KB Output is correct