Submission #116380

#	Time	Username	Problem	Language	Result	Execution time	Memory
116380		zubec	Mechanical Doll (IOI18_doll)	C++14	0 / 100	1 ms	276 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];

int kolsons = 1;

void add(int v, int l, int r, int x){
    if (l == r){
        //cout << "kek " << v << ' ' << v/2-sz/2+1 << ' ' << x << endl;
        if (v % 2)
            pr[v/2-sz/2+1].first = x; else
            pr[v/2-sz/2+1].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];

vector <int> vec;

void dfs(int v, int l, int r){
    if (l == r)
        return;
    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(pr[v].first, l, mid);
        if (!used[pr[v].first])
            bb = 1;
    }
    if (pr[v].second != -1){
        dfs(pr[v].second, mid+1, r);
        if (!used[pr[v].second])
            bb = 1;
    }
    if (bb == 0)
        used[v] = 1;
    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());
    for (int i = 1; i <= kolsons; i++){
        if (pr[i].first != -1){
            pr[i].first = -(lower_bound(vec.begin(), vec.end(), abs(pr[i].first))-vec.begin()+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);
    }

    answer(C, X, Y);
}

/**

4 4
1 2 1 3

*/

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