Submission #995437

#	Time	Username	Problem	Language	Result	Execution time	Memory
995437		shiomusubi496	Mechanical Doll (IOI18_doll)	C++17	53 / 100	96 ms	17708 KiB

doll

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

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)
#define all(v) begin(v), end(v)

using namespace std;

using ll = long long;

template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }

void create_circuit(int M, std::vector<int> A) {
    int N = A.size();
    vector<vector<int>> B(M + 1);
    rep (i, N) B[A[i]].push_back(i);
    vector<int> C(M + 1);
    C[0] = A[0];
    int cur = 1;
    int lst = -1;
    vector<pair<int, int>> memo;
    rep2 (i, 1, M + 1) {
        if (B[i].empty()) {
            C[i] = 0;
            continue;
        }
        if (B[i].size() == 1) {
            if (B[i][0] < N - 1) C[i] = A[B[i][0] + 1];
            else lst = i;
            continue;
        }
        int lev = 0;
        while ((1 << lev) < B[i].size()) ++lev;
        if ((1 << lev) != B[i].size()) {
            memo.emplace_back(i, -1);
        }
        int r = 1;
        auto dfs = [&](auto&& dfs, int v, vector<int> p, int lev, bool f) -> void {
            if (p.empty() && !f) {
                C[v] = r;
                return;
            }
            if (lev == 0) {
                if (p.empty()) {
                    if (f) memo.back().second = v;
                    else C[v] = r;
                }
                else {
                    assert(p.size() == 1);
                    if (p[0] < N - 1) C[v] = A[p[0] + 1];
                    else lst = v;
                }
                return;
            }
            vector<int> p0, p1;
            rep (i, p.size()) {
                if (i % 2 == 0) p0.push_back(p[i]);
                else p1.push_back(p[i]);
            }
            int t = cur++;
            if (r == 1) r = -t;
            C.push_back(0); C.push_back(0);
            C[v] = -t;
            int tmp = C.size();
            dfs(dfs, tmp - 2, p0, lev - 1, false);
            dfs(dfs, tmp - 1, p1, lev - 1, f);
        };
        dfs(dfs, i, B[i], lev, true);
        if ((1 << lev) != B[i].size()) memo.back().first = r;
    }
    {
        if (memo.empty()) C[lst] = 0;
        else {
            C[lst] = memo[0].first;
            rep (i, memo.size() - 1) {
                C[memo[i].second] = memo[i + 1].first;
            }
            C[memo.back().second] = 0;
        }
    }
    vector<int> X(cur - 1), Y(cur - 1);
    rep (i, cur - 1) {
        X[i] = C[M + 1 + i * 2];
        Y[i] = C[M + 1 + i * 2 + 1];
    }
    C.resize(M + 1);
    answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:37:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         while ((1 << lev) < B[i].size()) ++lev;
      |                ~~~~~~~~~~~^~~~~~~~~~~~~
doll.cpp:38:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         if ((1 << lev) != B[i].size()) {
      |             ~~~~~~~~~~~^~~~~~~~~~~~~~
doll.cpp:73:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         if ((1 << lev) != B[i].size()) memo.back().first = r;
      |             ~~~~~~~~~~~^~~~~~~~~~~~~~

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