Submission #713823

#	Time	Username	Problem	Language	Result	Execution time	Memory
713823		PixelCat	Mechanical Doll (IOI18_doll)	C++14	100 / 100	83 ms	9888 KiB

doll

#ifdef NYAOWO
#include "grader.cpp"
#endif
#include "doll.h"

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXM = 100010;

vector<int> x, y;

int solve(vector<int> &v, int l, int r, int n) {
    if(r < n) return -1;
    if(l == r) return v[l];
    int m = (l + r) / 2;
    int id = sz(x);
    x.eb(0); y.eb(0);
    // int a = solve(v, m + 1, r, n);
    int a = solve(v, l, m, n);
    // int b = solve(v, l, m, n);
    int b = solve(v, m + 1, r, n);
    x[id] = a; y[id] = b;
    // cout << l << " " << r << " " << id << " " << x[id] << " " << y[id] << " " << (-(id + 1)) << "\n" << flush;
    return -(id + 1);
}

void rev(int n, vector<int> &v) {
    int j = 0;
    For(i, 0, n - 1) {
        if(i < j) swap(v[i], v[j]);
        for(int k = n >> 1; (j ^= k) < k; k >>= 1);
    }
}

void create_circuit(int M, std::vector<int> A) {
    // if(M == 1) {
    //     solve2(sz(A));
    //     return;
    // }
    int lgn = __lg(sz(A) - 1) + 1;
    int n = (1 << lgn);

    A.eb(0);
    vector<int> ans(M + 1, -1);
    reverse(all(A));
    ans[0] = A.back();
    A.pop_back();

    vector<int> b(n);
    For(i, 0, n - 1) b[i] = i;
    rev(n, b);
    b.erase(b.begin() + sz(A), b.end());
    sort(all(b));
    vector<int> c(n, -1);
    For(i, 0, sz(A) - 1) {
        c[b[i]] = A[i];
    }
    rev(n, c);
    reverse(all(c));

    solve(c, 0, n - 1, n - sz(A));
    answer(ans, x, y);
}


/*

4 16
1 2 1 3 1 3 1 1 2 1 3 1 3 1 4 4

1 13
1 1 1 1 1 1 1 1 1 1 1 1 1

*/

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