Submission #116391

#	Time	Username	Problem	Language	Result	Execution time	Memory
116391		zubec	Mechanical Doll (IOI18_doll)	C++14	0 / 100	1 ms	204 KiB

doll

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

const int N = 200100;

int dir[N*4], n, sz;

pair<int, int> pr[N*4];

int kolsons = 1;

void add(int v, int l, int r, int x){
    if (l == r){
        //cout << "kek " << v << ' ' << v/2 << ' ' << x << endl;
        if (v % 2 == 0)
            pr[v/2].first = x; else
            pr[v/2].second = x;
        return;
    }
    int mid = (l+r)>>1;
    if (dir[v] == 0){
        add(v+v, l, mid, x);
    } else {
        add(v+v+1, mid+1, r, x);
    }
    dir[v] ^= 1;
}

bool used[N*4];

vector <int> vec;

void dfs(int v, int l, int r){
    if (l == r)
        return;
    //cout << "kek " << v << ' ' << pr[v].first << ' ' << pr[v].second << endl;
    if (pr[v].first == -1 && pr[v].second == -1){
        used[v] = 1;
        return;
    }
    int mid = (l+r)>>1;
    bool bb = 0;
    if (pr[v].first != -1){
        dfs(v+v, l, mid);
        if (!used[v+v])
            bb = 1;
    }
    if (pr[v].second != -1){
        dfs(v+v+1, mid+1, r);
        if (!used[v+v+1])
            bb = 1;
    }
    if (bb == 0)
        used[v] = 1; else
        vec.push_back(v);
}

void create_circuit(int M, std::vector<int> A) {
    n = A.size();
    vector <int> C, X, Y;
    if (n == 1){
        C.push_back(A[0]);
        for (int i = 1; i <= M; i++)
            C.push_back(0);
        answer(C, X, Y);
        return;
    }
    kolsons = 1;
    sz = 1;
    while(sz < n)
        sz += sz;
    for (int i = 2; i <= n; i++){
        add(1, 1, sz, A[i-1]);
    }
    for (int i = n; i < sz; i++){
        add(1, 1, sz, -1);
    }
    add(1, 1, sz, 0);
    dfs(1, 1, sz);
    C.push_back(A[0]);
    for (int i = 1; i <= M; i++)
        C.push_back(-1);
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    /*cout << "kek" << ' ' << vec.size() << endl;
    for (int i = 0; i < vec.size(); i++)
        cout << vec[i] << ' ';
    cout << endl;*/
    for (int i = 1; i <= sz/2-1; i++){
        pr[i].first = -(i+i);
        pr[i].second = -(i+i+1);
    }
    for (int i = 1; i <= sz-1; i++){
        if (used[i])
            continue;
        //cout << pr[i].first << ' ' << pr[i].second << endl;
        if (i <= sz/2-1){
            if (used[pr[i].first])
                pr[i].first = -1;
            if (pr[i].first != -1){
                pr[i].first = -(lower_bound(vec.begin(), vec.end(), abs(pr[i].first))-vec.begin()+1);
            }
            if (used[pr[i].second])
                pr[i].second = -1;
            if (pr[i].second != -1){
                pr[i].second = -(lower_bound(vec.begin(), vec.end(), abs(pr[i].second))-vec.begin()+1);
            }
        }
        X.push_back(pr[i].first);
        Y.push_back(pr[i].second);
    }
    /*cout << endl;
    for (int i = 0; i < X.size(); i++)
        cout << X[i] << ' ' << Y[i] << endl;*/

    answer(C, X, Y);
}

/**

4 5
1 2 1 3 1

*/

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