Submission #413527

#	Time	Username	Problem	Language	Result	Execution time	Memory
413527		xyz	Mechanical Doll (IOI18_doll)	C++17	100 / 100	253 ms	12180 KiB

doll

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

const int N = 3e5;
int to[N];
bool done[N][2];

vector<pair<int, int>> sw; // switches

int build(int l, int r, int k){
    if(l > r)
        return 1;
    int v = sw.size();
    sw.push_back({-1, -1});
    if(k <= 0){
        done[v][1] = true;
        if(r - l == 1)
            done[v][0] = true;
    }
    if(r - l + 1 <= 2 && k <= 0)
        return v;
    assert(k >= 0);
    sw[v].second = -build(max(l, r - (1 << k) + 1), r, k - 1);
    sw[v].first = -build(l, r - (1 << k), k - 1);
    return v;
}

void create_circuit(int M, vector<int> A) {
    int n = A.size();

    const int Q = 99999999;
    sw.push_back({Q, Q}); // just to make 1-idx
    vector<int> out(M + 1);
    A.push_back(0);
    for(int i = n - 1; i >= 0; i --)
        swap(A[i], A[i + 1]);
    ++ n;
    A.push_back(0);

    int k = 0;
    while((1 << (k + 1)) < n)
        ++ k;
    int start = build(0, n - 1, k);
    for(int i = 1; i < sw.size(); i ++){
        done[i][0] ^= 1;
        done[i][1] ^= 1;
    }
    for(int j = 0; j < n; j ++){
        int v = start;
        bool found = false;
        while(!found){
            int was = v;
            if(to[v] == 1){
                if(sw[v].second == -start && !done[v][1]){
                    found = true;
                    done[v][1] = true;
                    sw[v].second = A[j + 1];
                }else{
                    v = -sw[v].second;
                }
            }else{
                if(sw[v].first == -start && !done[v][0]){
                    found = true;
                    done[v][0] = true;
                    sw[v].first = A[j + 1];
                }else{
                    v = -sw[v].first;
                }
            }
            to[was] ^= 1;
        }
    }

    for(int i = 0; i <= M; i ++)
        out[i] = -start;
    int S = sw.size();
    vector<int> X(S - 1), Y(S - 1);
    for(int i = 1; i < S; i ++)
        X[i - 1] = sw[i].first, Y[i - 1] = sw[i].second;
    answer(out, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i = 1; i < sw.size(); i ++){
      |                    ~~^~~~~~~~~~~

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