Submission #1068396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068396		TheQuantiX	Mechanical Doll (IOI18_doll)	C++17	37 / 100	139 ms	10816 KiB

doll

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

using namespace std;
using ll = long long;

constexpr ll INF = 1000000000;

ll conn;
set<ll> st;
ll nxt = -2;

void connect(ll x, vector<int> &X, vector<int> &Y, ll idx) {
    // cout << x << '\n';
    if (X[idx] == 0) {
        X[idx] = x;
    }
    else {
        Y[idx] = x;
    }
}

void distribute(ll sz, vector<int> &X, vector<int> &Y, vector<int> &A, ll idx) {
    // cout << idx << ' ' << sz << ' ' << ex << endl;
    if (idx >= X.size()) {
        X.resize(idx + 1);
    }
    if (idx >= Y.size()) {
        Y.resize(idx + 1);
    }
    // cout << sz << ' ' << e << '\n';
    X[idx] = 0;
    Y[idx] = 0;
    if (sz == 2) {
        connect(INF, X, Y, idx);
        connect(INF, X, Y, idx);
        return;
    }
    X[idx] = nxt;
    nxt--;
    Y[idx] = nxt;
    nxt--;
    distribute(sz - sz / 2, X, Y, A, -X[idx] - 1);
    distribute(sz / 2, X, Y, A, -Y[idx] - 1);
}

void create_circuit(int M, vector<int> A) {
    ll NN = A.size();
    A.push_back(-1);
    ll N = A.size();
    ll y = 0;
    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);
    }
    distribute(N, X, Y, A, 0);
    // for (int i = 0; i < C.size(); i++) {
    //     cout << C[i] << '\n';
    // }
    // cout << conn << '\n';
    while (!st.empty()) {
        ll x = *st.begin();
        st.erase(x);
        Y[conn] = -x - 1;
        conn = x;
    }
    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 {
        // cout << pos << endl;
        if (pos >= 0) {
            pos = C[pos];
        }
        else {
            // cout << '\t' << state[-pos - 1] << endl;
            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;
    // }
    assert(X.size() <= NN * 2);
    answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void distribute(ll, std::vector<int>&, std::vector<int>&, std::vector<int>&, ll)':
doll.cpp:25:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     if (idx >= X.size()) {
      |         ~~~~^~~~~~~~~~~
doll.cpp:28:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     if (idx >= Y.size()) {
      |         ~~~~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:56: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]
   56 |     while (A.size() < ex) {
      |            ~~~~~~~~~^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from doll.cpp:1:
doll.cpp:108: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]
  108 |     assert(X.size() <= NN * 2);
      |            ~~~~~~~~~^~~~~~~~~
doll.cpp:51:8: warning: unused variable 'y' [-Wunused-variable]
   51 |     ll y = 0;
      |        ^

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