Submission #603289

#	Time	Username	Problem	Language	Result	Execution time	Memory
603289		AlperenT	Mechanical Doll (IOI18_doll)	C++17	84 / 100	1083 ms	7344 KiB

doll

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

using namespace std;

const int INF = 1e9 + 5;

void create_circuit(int m, vector<int> a) {
    int n, k;

    n = a.size(), k = __lg(n);

    vector<int> c(m + 1), x(n + k + 1, INF), y(n + k + 1, INF);

    for(int i = 0; i <= m; i++) c[i] = -1;

    int cur = k + 2;

    for(int i = k; i >= 0; i--){
        if(n & (1 << i)){
            x[(k - i) + 1] = -cur;
            y[(k - i) + 1] = (i == 0 ? -cur : -((k - i) + 2));

            for(int len = 0; len < i - 1; len++){
                for(int j = 0; j < (1 << len); j++){
                    x[cur] = -(cur + (1 << len) + j);

                    y[cur] = -(cur + (1 << len) + 1 + j);

                    cur++;
                }
            }

            cur += (1 << i) / 2;
        }
        else{
            x[(k - i) + 1] = -1;
            y[(k - i) + 1] = (i == 0 ? 0 : -((k - i) + 2));
        }
    }

    if(n & 1) y[-x[k + 1]] = 0;

    vector<char> where(n + k + 1, 'X');

    int v = -1;

    for(int i = 0; i < n; i++){
        if(v > 0) v = c[v];

        while(v < 0){
            if(where[-v] == 'X'){
                where[-v] = 'Y';

                if(x[-v] == INF) x[-v] = a[i];

                v = x[-v];
            }
            else if(where[-v] == 'Y'){
                where[-v] = 'X';
                
                if(y[-v] == INF) y[-v] = a[i];

                v = y[-v];
            }
        }
    }

    for(auto &i : x) if(i == INF) i = -1;
    for(auto &i : y) if(i == INF) i = -1;

    x.erase(x.begin());
    y.erase(y.begin());

    answer(c, x, y);
}

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