Submission #120570

#	Time	Username	Problem	Language	Result	Execution time	Memory
120570		onjo0127	Mechanical Doll (IOI18_doll)	C++11	0 / 100	7 ms	4428 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

bool chk[500009];
int N, k, ord[500009], cnt, L[500009], R[500009];
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);
    ++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] = -1;
        else X[idx-1] = A[ord[idx*2+1]];
        if(ord[idx*2] == -1) Y[idx-1] = -1;
        else Y[idx-1] = A[ord[idx*2]];
        return;
    }
    int m = s+e >> 1;
    Y[idx-1] = -(idx*2);
    dfs(idx*2, s, m);
    if(!chk[idx*2+1]) {
        X[idx-1] = -(idx*2+1);
        dfs(idx*2+1, m+1, e);
    }
    else X[idx-1] = -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<X.size(); i++) {
        if(X[i] < 0) X[i] = -(lower_bound(T.begin(), T.end(), -X[i]) - T.begin() + 1);
        if(Y[i] < 0) Y[i] = -(lower_bound(T.begin(), T.end(), -Y[i]) - T.begin() + 1);
    }
    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;
      |             ~^~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=0; i<X.size(); i++) {
      |                  ~^~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56