Submission #120740

#	Time	Username	Problem	Language	Result	Execution time	Memory
120740		onjo0127	Mechanical Doll (IOI18_doll)	C++11	100 / 100	195 ms	18060 KiB

doll

#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 (stderr)

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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56