Submission #388328

#	Time	Username	Problem	Language	Result	Execution time	Memory
388328		ryno	Mechanical Doll (IOI18_doll)	C++14	0 / 100	143 ms	10144 KiB

doll

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include "doll.h"
using namespace std;

vector<int> C, X, Y;
bool toggled[4000005];
int lChild[4000005], rChild[4000005];
int S, MAX, ID = 1;

void push(int node) {
    if (lChild[node] == 0) {
        ++ID;
        lChild[node] = ID;
    }
    if (rChild[node] == 0) {
        ++ID;
        rChild[node] = ID;
    }
}

int& getChild(int node) {
    if (toggled[node]) return rChild[node];
    return lChild[node];
}

bool _query(int val, int node = 1, int l = 1, int r = MAX) {
    if (l == r) {
        if (node < 10) throw 20;
        getChild(node) = val;
        toggled[node] ^= 1;

        return true;
    }

    else if (ID == S+1 && (lChild[node] == 0 || rChild[node] == 0)) {
        getChild(node) = 1;
        toggled[node] ^= 1;

        return false; // return _query(val, 1);
    }

    else {
        push(node);
        int m = (l + r) / 2;
        int child = getChild(node);
        toggled[node] ^= 1;
        if (child == 1) return false; // return _query(val, 1);
        if (child == lChild[node]) return _query(val, lChild[node], l, m);
        else if (child == rChild[node]) return _query(val, rChild[node], m + 1, r);

        return true;
    }
}

void query(int val) {
    do {
        continue;
    } while (!_query(val));
}

void create_circuit(int M, vector<int> A) {
    int N = A.size();
    C.push_back(A[0]);
    for (int i = 1; i <= M; ++i) C.push_back(-1);
    
    S = N + ceil(log2(N));
    MAX = 1 << int(ceil(log2(N)-1));
    for (int i = 1; i < 2 * MAX; ++i) {
        if (i < A.size()) query(-A[i]);
        else query(1);
    }
    query(0);

    for (int i = 1; i <= ID; ++i) {
        X.push_back(-lChild[i]);
        Y.push_back(-rChild[i]);
    }
    answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:72:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         if (i < A.size()) query(-A[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