Submission #1068623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068623		TheQuantiX	Mechanical Doll (IOI18_doll)	C++17	37 / 100	99 ms	8772 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"

using namespace std;
using ll = long long;

constexpr ll INF = 1000000000 - 1;

ll nxt = -2;

void create_circuit(int M, vector<int> A) {
    ll NN = A.size();
    A.push_back(-1);
    ll N = A.size();
    ll ex = 1;
    while (ex < N) {
        ex *= 2;
    }
    while (A.size() < ex) {
        A.push_back(-1);
    }
    N = A.size();
    A[N - 1] = 0;
    vector<int> C, X, Y;
    C.push_back(-1);
    for (int i = 0; i < M; i++) {
        C.push_back(-1);
    }
    X.resize(N - 1);
    Y.resize(N - 1);
    for (int i = 1; i < N / 2; i++) {
        X[i - 1] = -(i * 2);
        Y[i - 1] = -(i * 2 + 1);
    }
    for (int i = N / 2; i <= N - 1; i++) {
        X[i - 1] = INF;
        Y[i - 1] = INF;
    }
    // for (int i = 0; i < C.size(); i++) {
    //     cout << C[i] << '\n';
    // }
    // cout << conn << '\n';
    ll pos = 0, cnt = 0;
    vector<bool> state(X.size());
    // for (int i = 0; i < X.size(); i++) {
    //     cout << X[i] << ' ' << Y[i] << endl;
    // }
    do {
        if (pos >= 0) {
            pos = C[pos];
        }
        else {
            if (state[-pos - 1] == 0) {
                if (X[-pos - 1] == INF) {
                    X[-pos - 1] = A[cnt++];
                }
                state[-pos - 1] = !state[-pos - 1];
                pos = X[-pos - 1];
            }
            else {
                if (Y[-pos - 1] == INF) {
                    Y[-pos - 1] = A[cnt++];
                }
                state[-pos - 1] = !state[-pos - 1];
                pos = Y[-pos - 1];
            }
        }
    } while (pos != 0);
    // for (int i = 0; i < X.size(); i++) {
    //     cout << '\t' << X[i] << ' ' << Y[i] << endl;
    // }
    if (X.size() > NN * 2) {
        exit(-1);
        // C[0] = 0;
    }
    answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:19:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   19 |     while (A.size() < ex) {
      |            ~~~~~~~~~^~~~
doll.cpp:72:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   72 |     if (X.size() > NN * 2) {
      |         ~~~~~~~~~^~~~~~~~

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