Submission #776292

#	Time	Username	Problem	Language	Result	Execution time	Memory
776292		anha3k25cvp	Library (JOI18_library)	C++14	100 / 100	311 ms	492 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, g;
vector <vector <int>> adj;

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 add_edge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void Solve(int n) {
    root.assign(n + 1, 0);
    l.assign(n + 1, 0);
    r.assign(n + 1, 0);
    adj.resize(n + 1);
    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;
            add_edge(u, i);
            if (u == l[ru])
                l[ru] = i;
            else
                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(l[ru], r[ru]);
            if (v == r[rv])
                swap(l[rv], r[rv]);
            root[i] = ru;
            root[rv] = ru;
            r[ru] = r[rv];
            add_edge(u, i);
            add_edge(v, i);
        }
    }
    for (int i = 1; i <= n; i ++)
        if (get(i) == i) {
            vector <int> ans(n, 0), vis(n + 1, 0);
            int u = l[i];
            for (int j = 0; j < n; j ++) {
                vis[u] = 1;
                ans[j] = u;
                int u_ = 0;
                for (int v : adj[u])
                    if (!vis[v])
                        u_ = v;
                u = u_;
            }
            Answer(ans);
            return;
        }
}

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