oj.uz

Submission #566122

# Submission time Handle Problem Language Result Execution time Memory
566122 2022-05-21T20:47:14 Z piOOE ICC (CEOI16_icc) C++17
61 / 100
 186 ms 624 KB 
#include "icc.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)
#define sz(x) ((int)size(x))
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int ask(vector<int> a, vector<int> b) {
    for (int &x: a) ++x;
    for (int &y: b) ++y;
    return query(sz(a), sz(b), a.data(), b.data());
}

vector<int> p;

int get(int a) {
    return a == p[a] ? a : p[a] = get(p[a]);
}

bool mrg(int a, int b) {
    a = get(a), b = get(b);
    if (a == b) {
        return false;
    }
    p[b] = a;
    return true;
}

void run(int n) {
    p.resize(n);
    iota(all(p), 0);
    for (int cnt = 1; cnt < n; ++cnt) {
        vector<int> v;
        for (int i = 0; i < n; ++i) {
            if (p[i] == i) v.push_back(i);
        }
        while (true) {
            vector<int> aa, bb, a, b;
            for (int i = 0; i < sz(v); ++i) {
                if ((rnd() & 1) == (i & 1)) aa.push_back(v[i]);
                else bb.push_back(v[i]);
            }
            for (int x: aa) {
                for (int i = 0; i < n; ++i)
                    if (get(i) == x)
                        a.push_back(i);
            }

            for (int x: bb) {
                for (int i = 0; i < n; ++i)
                    if (get(i) == x)
                        b.push_back(i);
            }

            if (!a.empty() && !b.empty() && ask(a, b)) {
                int l = -1, r = sz(a) - 1;
                while (l + 1 < r) {
                    vector<int> cc;
                    int m = (l + r) >> 1;
                    for (int i = 0; i <= m; ++i) cc.push_back(a[i]);
                    if (!ask(cc, b)) l = m;
                    else r = m;
                }
                int v1 = a[r];
                l = -1, r = sz(b) - 1;
                while (l + 1 < r) {
                    vector<int> cc;
                    int m = (l + r) >> 1;
                    for (int i = 0; i <= m; ++i) cc.push_back(b[i]);
                    if (!ask(a, cc)) l = m;
                    else r = m;
                }
                int v2 = b[r];
                mrg(v1, v2);
                setRoad(v1 + 1, v2 + 1);
                break;
            }
        }
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 468 KB Ok! 110 queries used.
2 Correct 5 ms 468 KB Ok! 107 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 468 KB Ok! 546 queries used.
2 Correct 48 ms 480 KB Ok! 838 queries used.
3 Correct 47 ms 468 KB Ok! 828 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 488 KB Ok! 1533 queries used.
2 Correct 186 ms 484 KB Ok! 2154 queries used.
3 Correct 148 ms 480 KB Ok! 1733 queries used.
4 Correct 142 ms 504 KB Ok! 1720 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 600 KB Ok! 1671 queries used.
2 Correct 137 ms 624 KB Ok! 1649 queries used.
3 Correct 178 ms 504 KB Ok! 1861 queries used.
4 Correct 128 ms 468 KB Ok! 1587 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 496 KB Too many queries! 1954 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 171 ms 484 KB Too many queries! 1958 out of 1625
2 Halted 0 ms 0 KB -