Submission #1144732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144732		Issa	Mechanical Doll (IOI18_doll)	C++20	100 / 100	69 ms	9404 KiB

doll

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

const int maxn = 1e6 + 100;

int sz;
int x[maxn];
int y[maxn];

void go(int &v, int num){
    if(!v) v = num;
    else{
        swap(x[v], y[v]);
        go(y[v], num);
    }
}

int build(int l, int k){
    if(!k) return 1;
    if(!l) return 0;
    int v = ++sz, val = min((1<<(l-1)), k);
    x[v] = build(l-1, val);
    y[v] = build(l-1, k - val);
    if(y[v] == 1) swap(y[v], x[v]);
    return v;
}

void create_circuit(int M, std::vector<int> A) {
    int k = 0;
    while((1<<k) < A.size()) k++;
    int r = build(k, A.size());
    // for(int i = 1; i <= sz; i++){
    //     cout << i << ' ' << x[i] << ' ' << y[i] << endl;
    // }
    for(int i = 1; i < A.size(); i++){
        go(r, -A[i]);
    } go(r, 0);
    vector<int> C = {A[0]}, X, Y;
    for(int i = 0; i < M; i++){
        C.push_back(-r);
    } for(int i = 1; i <= sz; i++){
        X.push_back(-x[i]);
        Y.push_back(-y[i]);
    } 
    // for(int x: C) cout << x << ' '; cout << '\n';
    // for(int x: X) cout << x << ' '; cout << '\n';
    // for(int x: Y) cout << x << ' '; cout << '\n';
    answer(C, X, Y);
}

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