oj.uz

Submission #120740

# Submission time Handle Problem Language Result Execution time Memory
120740 2019-06-25T11:15:23 Z onjo0127 Mechanical Doll (IOI18_doll) C++11
100 / 100
 195 ms 18060 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

bool chk[1000009], TC[1000009];
int N, k, ord[1000009], cnt, x[1000009], y[1000009];
vector<int> A, S, C, X, Y, T;

void go(int idx, int s, int e, int mn, int d) {
    if(s > N) {
        chk[idx] = 1;
        return;
    }
    if(idx >= k) {
        ord[idx] = mn;
        S.push_back(mn);
        return;
    }
    T.push_back(idx); TC[idx] = 1;
    ++cnt;
    int m = s+e >> 1;
    go(idx*2, s, m, mn + (1<<d), d+1);
    go(idx*2+1, m+1, e, mn, d+1);
}

void dfs(int idx, int s, int e) {
    if(s > N) return;
    if(idx*2 >= k) {
        if(ord[idx*2+1] == -1) x[idx] = -1;
        else x[idx] = A[ord[idx*2+1]];
        if(ord[idx*2] == -1) y[idx] = -1;
        else y[idx] = A[ord[idx*2]];
        return;
    }
    int m = s+e >> 1;
    y[idx] = -(idx*2);
    dfs(idx*2, s, m);
    if(!chk[idx*2+1]) {
        x[idx] = -(idx*2+1);
        dfs(idx*2+1, m+1, e);
    }
    else x[idx] = -1;
}

void create_circuit(int M, vector<int> A) {
    A.push_back(0); ::A = A;
    N = ::A.size();
    C.resize(M+1);
    for(int i=0; i<=M; i++) C[i] = -1;
    for(k=1; k<N; k*=2);
    memset(ord, -1, sizeof(ord));
    go(1, 1, k, 1, 0);
    sort(S.begin(), S.end());
    for(int i=1; i<=2*k; i++) if(ord[i] != -1) {
        ord[i] = lower_bound(S.begin(), S.end(), ord[i]) - S.begin();
    }
    X.resize(cnt); Y.resize(cnt);
    dfs(1, 1, k);
    sort(T.begin(), T.end());
    for(int i=0; i<2*k; i++) {
        if(TC[i]) {
            int idx = lower_bound(T.begin(), T.end(), i) - T.begin();
            X[idx] = (x[i] < 0 ? -(lower_bound(T.begin(), T.end(), -x[i]) - T.begin() + 1) : x[i]);
            Y[idx] = (y[i] < 0 ? -(lower_bound(T.begin(), T.end(), -y[i]) - T.begin() + 1) : y[i]);
        }
    }
    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void go(int, int, int, int, int)':
doll.cpp:21:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     int m = s+e >> 1;
      |             ~^~
doll.cpp: In function 'void dfs(int, int, int)':
doll.cpp:35:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int m = s+e >> 1;
      |             ~^~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 62 ms 9560 KB Output is correct
3 Correct 58 ms 9500 KB Output is correct
4 Correct 3 ms 4172 KB Output is correct
5 Correct 14 ms 5324 KB Output is correct
6 Correct 88 ms 11908 KB Output is correct
7 Correct 4 ms 4172 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 62 ms 9560 KB Output is correct
3 Correct 58 ms 9500 KB Output is correct
4 Correct 3 ms 4172 KB Output is correct
5 Correct 14 ms 5324 KB Output is correct
6 Correct 88 ms 11908 KB Output is correct
7 Correct 4 ms 4172 KB Output is correct
8 Correct 145 ms 13248 KB Output is correct
9 Correct 121 ms 13764 KB Output is correct
10 Correct 168 ms 18060 KB Output is correct
11 Correct 4 ms 4172 KB Output is correct
12 Correct 3 ms 4172 KB Output is correct
13 Correct 4 ms 4172 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 62 ms 9560 KB Output is correct
3 Correct 58 ms 9500 KB Output is correct
4 Correct 3 ms 4172 KB Output is correct
5 Correct 14 ms 5324 KB Output is correct
6 Correct 88 ms 11908 KB Output is correct
7 Correct 4 ms 4172 KB Output is correct
8 Correct 145 ms 13248 KB Output is correct
9 Correct 121 ms 13764 KB Output is correct
10 Correct 168 ms 18060 KB Output is correct
11 Correct 4 ms 4172 KB Output is correct
12 Correct 3 ms 4172 KB Output is correct
13 Correct 4 ms 4172 KB Output is correct
14 Correct 159 ms 17444 KB Output is correct
15 Correct 113 ms 12752 KB Output is correct
16 Correct 168 ms 17296 KB Output is correct
17 Correct 4 ms 4172 KB Output is correct
18 Correct 4 ms 4172 KB Output is correct
19 Correct 4 ms 4172 KB Output is correct
20 Correct 163 ms 17764 KB Output is correct
21 Correct 3 ms 4172 KB Output is correct
22 Correct 4 ms 4252 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 102 ms 11712 KB Output is correct
3 Correct 98 ms 11720 KB Output is correct
4 Correct 155 ms 15748 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 102 ms 11712 KB Output is correct
3 Correct 98 ms 11720 KB Output is correct
4 Correct 155 ms 15748 KB Output is correct
5 Correct 154 ms 17128 KB Output is correct
6 Correct 161 ms 16772 KB Output is correct
7 Correct 157 ms 16924 KB Output is correct
8 Correct 154 ms 16540 KB Output is correct
9 Correct 97 ms 11752 KB Output is correct
10 Correct 151 ms 16452 KB Output is correct
11 Correct 195 ms 16116 KB Output is correct
12 Correct 120 ms 11964 KB Output is correct
13 Correct 115 ms 12392 KB Output is correct
14 Correct 116 ms 12500 KB Output is correct
15 Correct 104 ms 12648 KB Output is correct
16 Correct 5 ms 4484 KB Output is correct
17 Correct 98 ms 12228 KB Output is correct
18 Correct 101 ms 12092 KB Output is correct
19 Correct 106 ms 11984 KB Output is correct
20 Correct 154 ms 16388 KB Output is correct
21 Correct 159 ms 16056 KB Output is correct
22 Correct 157 ms 16184 KB Output is correct