Submission #776287

#	Time	Username	Problem	Language	Result	Execution time	Memory
776287		anha3k25cvp	Library (JOI18_library)	C++14	0 / 100	22 ms	208 KiB

library

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>
#include "library.h"

using namespace std;

vector <int> root, l, r, nex, g;

int get(int u) {
    return (u == root[u] ? u : root[u] = get(root[u]));
}

int tknp1(int l, int r, int n, int pos) {
    if (l == r)
        return g[l];
    int mid = (l + r) / 2;
    vector <int> a(n, 0);
    for (int i = l; i <= mid; i ++)
        a[g[i] - 1] = 1;
    int cnt = Query(a);
    a[pos - 1] = 1;
    int cnt_ = Query(a);
    if (cnt_ == cnt)
        return tknp1(l, mid, n, pos);
    return tknp1(mid + 1, r, n, pos);
}

II tknp2(int l, int r, int n, int pos) {
    int mid = (l + r) / 2;
    vector <int> a(n, 0);
    for (int i = l; i <= mid; i ++)
        a[g[i] - 1] = 1;
    int cnt = Query(a);
    a[pos - 1] = 1;
    int cnt_ = Query(a);
    if (cnt_ == cnt - 1)
        return tknp2(l, mid, n, pos);
    if (cnt_ == cnt + 1)
        return tknp2(mid + 1, r, n, pos);
    return {tknp1(l, mid, n, pos), tknp1(mid + 1, r, n, pos)};
}

void Solve(int n) {
    root.assign(n + 1, 0);
    l.assign(n + 1, 0);
    r.assign(n + 1, 0);
    nex.assign(n + 1, 0);
    for (int i = 1; i <= n; i ++) {
        root[i] = i;
        l[i] = i;
        r[i] = i;
    }
    for (int i = 2; i <= n; i ++) {
        g.clear();
        vector <int> a(n, 0);
        for (int u = 1; u < i; u ++)
            if (get(u) == u) {
                a[l[u] - 1] = 1;
                g.push_back(l[u]);
                if (r[u] != l[u]) {
                    a[r[u] - 1] = 1;
                    g.push_back(r[u]);
                }
            }
        int cnt = Query(a);
        a[i - 1] = 1;
        int cnt_ = Query(a);
        if (cnt_ == cnt + 1);
        else if (cnt_ == cnt) {
            int u = tknp1(0, g.size() - 1, n, i), ru = get(u);
            root[i] = u;
            if (u == l[ru]) {
                nex[i] = u;
                l[ru] = i;
            }
            else {
                nex[u] = i;
                r[ru] = i;
            }
        }
        else {
            auto z = tknp2(0, g.size() - 1, n, i);
            int u = z.st, v = z.nd, ru = get(u), rv = get(v);
            if (u == l[ru]) {
                swap(u, v);
                swap(ru, rv);
            }
            root[i] = ru;
            root[rv] = ru;
            r[ru] = r[rv];
            nex[u] = i;
            nex[i] = v;
        }
    }
    for (int i = 1; i <= n; i ++)
        if (get(i) == i) {
            vector <int> ans(n, 0);
            int u = l[i];
            for (int j = 0; j < n; j ++) {
                ans[j] = u;
                u = nex[u];
            }
            Answer(ans);
            return;
        }
}

• Subtask 1: 0 / 19
• Subtask 2: 0 / 81