oj.uz

Submission #115180

# Submission time Handle Problem Language Result Execution time Memory
115180 2019-06-05T21:39:42 Z MladenP Mechanical Doll (IOI18_doll) C++17
100 / 100
 182 ms 18304 KB 
#include "doll.h"
#include <bits/stdc++.h>
#define MAXN (1<<20)
#define MAXM 200010
#define PRINT(x) cerr<<#x<<' '<<x<<endl;
#define mid (l+r)/2
#define pb push_back
using namespace std;
vector<int> X, Y, C, v;
int x[MAXN], y[MAXN], stdva, idxx[MAXN], N, idx;
void ubaci(int node, int put, int kraj, int dub) {
    if(dub == stdva) {
        if(put == 0) x[node] = kraj;
        if(put == 1) y[node] = kraj;
        return;
    }
    if(!(put&1)) {
        if(x[node] == -1) x[node] = --idx;
        ubaci(-x[node], put>>1, kraj, dub+1);
    } else {
        if(y[node] == -1) y[node] = --idx;
        ubaci(-y[node], put>>1, kraj, dub+1);
    }
}
void nadji(int put, int kraj, int l, int r) {
    if(l == r) {
        idxx[l] = kraj;
        return;
    }
    if(!(put&1)) nadji(put>>1, kraj, l, mid);
    else nadji(put>>1, kraj, mid+1, r);
}
void create_circuit(int M, std::vector<int> A) {
    N = A.size();
    C.resize(M+1);
    for(int i = 1; i <= M; i++) C[i] = -1;
    C[0] = -1;
    idx = -1;
    for(int i = 0; i < 20; i++) {
        if((1<<i) > N) {
            stdva = i;
            break;
        }
    }
    for(int i = 0; i < (1<<stdva); i++) {
        nadji(i, i, 0, (1<<stdva)-1);
    }
    fill(x, x+MAXN, -1);
    fill(y, y+MAXN, -1);
    int st = (1<<stdva)-N-1;
    for(int i = st; i < (1<<stdva)-1; i++) v.pb(idxx[i]);
    sort(v.begin(), v.end());
    for(int i = 0; i < N; i++) ubaci(1, v[i], A[i], 1);
    ubaci(1, (1<<stdva)-1, 0, 1);
    idx = -idx;
    X.resize(idx);
    Y.resize(idx);
    for(int i = 1; i <= idx; i++) {
        X[i-1] = x[i];
        Y[i-1] = y[i];
    }
    answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8396 KB Output is correct
2 Correct 67 ms 12616 KB Output is correct
3 Correct 53 ms 12828 KB Output is correct
4 Correct 6 ms 8396 KB Output is correct
5 Correct 17 ms 9676 KB Output is correct
6 Correct 85 ms 13804 KB Output is correct
7 Correct 5 ms 8440 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8396 KB Output is correct
2 Correct 67 ms 12616 KB Output is correct
3 Correct 53 ms 12828 KB Output is correct
4 Correct 6 ms 8396 KB Output is correct
5 Correct 17 ms 9676 KB Output is correct
6 Correct 85 ms 13804 KB Output is correct
7 Correct 5 ms 8440 KB Output is correct
8 Correct 125 ms 15288 KB Output is correct
9 Correct 116 ms 16824 KB Output is correct
10 Correct 144 ms 18304 KB Output is correct
11 Correct 5 ms 8396 KB Output is correct
12 Correct 7 ms 8396 KB Output is correct
13 Correct 8 ms 8396 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8396 KB Output is correct
2 Correct 67 ms 12616 KB Output is correct
3 Correct 53 ms 12828 KB Output is correct
4 Correct 6 ms 8396 KB Output is correct
5 Correct 17 ms 9676 KB Output is correct
6 Correct 85 ms 13804 KB Output is correct
7 Correct 5 ms 8440 KB Output is correct
8 Correct 125 ms 15288 KB Output is correct
9 Correct 116 ms 16824 KB Output is correct
10 Correct 144 ms 18304 KB Output is correct
11 Correct 5 ms 8396 KB Output is correct
12 Correct 7 ms 8396 KB Output is correct
13 Correct 8 ms 8396 KB Output is correct
14 Correct 182 ms 17792 KB Output is correct
15 Correct 94 ms 15780 KB Output is correct
16 Correct 169 ms 17532 KB Output is correct
17 Correct 7 ms 8396 KB Output is correct
18 Correct 6 ms 8396 KB Output is correct
19 Correct 6 ms 8468 KB Output is correct
20 Correct 132 ms 18068 KB Output is correct
21 Correct 6 ms 8396 KB Output is correct
22 Correct 5 ms 8396 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8396 KB Output is correct
2 Correct 91 ms 14248 KB Output is correct
3 Correct 109 ms 14780 KB Output is correct
4 Correct 152 ms 16704 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8396 KB Output is correct
2 Correct 91 ms 14248 KB Output is correct
3 Correct 109 ms 14780 KB Output is correct
4 Correct 152 ms 16704 KB Output is correct
5 Correct 130 ms 17372 KB Output is correct
6 Correct 139 ms 17152 KB Output is correct
7 Correct 132 ms 17172 KB Output is correct
8 Correct 124 ms 16884 KB Output is correct
9 Correct 84 ms 14800 KB Output is correct
10 Correct 148 ms 16900 KB Output is correct
11 Correct 150 ms 16684 KB Output is correct
12 Correct 88 ms 15008 KB Output is correct
13 Correct 115 ms 14384 KB Output is correct
14 Correct 89 ms 15516 KB Output is correct
15 Correct 102 ms 15656 KB Output is correct
16 Correct 9 ms 8704 KB Output is correct
17 Correct 76 ms 13776 KB Output is correct
18 Correct 88 ms 14256 KB Output is correct
19 Correct 117 ms 15064 KB Output is correct
20 Correct 138 ms 16796 KB Output is correct
21 Correct 159 ms 16616 KB Output is correct
22 Correct 143 ms 16716 KB Output is correct