oj.uz

Submission #776292

# Submission time Handle Problem Language Result Execution time Memory
776292 2023-07-07T15:14:06 Z anha3k25cvp Library (JOI18_library) C++14
100 / 100
 311 ms 492 KB 
#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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 256 KB # of queries: 2262
2 Correct 28 ms 308 KB # of queries: 2274
3 Correct 23 ms 308 KB # of queries: 2378
4 Correct 31 ms 304 KB # of queries: 2424
5 Correct 23 ms 208 KB # of queries: 2372
6 Correct 29 ms 312 KB # of queries: 2394
7 Correct 30 ms 308 KB # of queries: 2410
8 Correct 22 ms 208 KB # of queries: 2254
9 Correct 27 ms 316 KB # of queries: 2402
10 Correct 9 ms 304 KB # of queries: 1376
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 2
13 Correct 0 ms 208 KB # of queries: 6
14 Correct 1 ms 208 KB # of queries: 10
15 Correct 1 ms 208 KB # of queries: 82
16 Correct 2 ms 208 KB # of queries: 196

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 256 KB # of queries: 2262
2 Correct 28 ms 308 KB # of queries: 2274
3 Correct 23 ms 308 KB # of queries: 2378
4 Correct 31 ms 304 KB # of queries: 2424
5 Correct 23 ms 208 KB # of queries: 2372
6 Correct 29 ms 312 KB # of queries: 2394
7 Correct 30 ms 308 KB # of queries: 2410
8 Correct 22 ms 208 KB # of queries: 2254
9 Correct 27 ms 316 KB # of queries: 2402
10 Correct 9 ms 304 KB # of queries: 1376
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 2
13 Correct 0 ms 208 KB # of queries: 6
14 Correct 1 ms 208 KB # of queries: 10
15 Correct 1 ms 208 KB # of queries: 82
16 Correct 2 ms 208 KB # of queries: 196
17 Correct 232 ms 380 KB # of queries: 16502
18 Correct 264 ms 384 KB # of queries: 16270
19 Correct 286 ms 492 KB # of queries: 16262
20 Correct 276 ms 372 KB # of queries: 15292
21 Correct 222 ms 464 KB # of queries: 14436
22 Correct 311 ms 376 KB # of queries: 16522
23 Correct 278 ms 460 KB # of queries: 16466
24 Correct 109 ms 328 KB # of queries: 7492
25 Correct 303 ms 476 KB # of queries: 16062
26 Correct 229 ms 492 KB # of queries: 14944
27 Correct 94 ms 328 KB # of queries: 7466
28 Correct 69 ms 340 KB # of queries: 3994
29 Correct 85 ms 344 KB # of queries: 3990
30 Correct 79 ms 336 KB # of queries: 3994