oj.uz

Submission #566130

# Submission time Handle Problem Language Result Execution time Memory
566130 2022-05-21T20:54:33 Z piOOE ICC (CEOI16_icc) C++17
61 / 100
 183 ms 500 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;
            vector<int> gg(sz(v));
            iota(all(gg), 0);
            shuffle(all(gg), rnd);
            for (int i = 0; i < sz(gg); ++i) {
                if (i < sz(gg) / 2) aa.push_back(v[gg[i]]);
                else bb.push_back(v[gg[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 5 ms 468 KB Ok! 106 queries used.
2 Correct 6 ms 468 KB Ok! 113 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 468 KB Ok! 556 queries used.
2 Correct 44 ms 468 KB Ok! 820 queries used.
3 Correct 46 ms 468 KB Ok! 813 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 480 KB Ok! 1528 queries used.
2 Correct 183 ms 492 KB Ok! 2120 queries used.
3 Correct 137 ms 468 KB Ok! 1676 queries used.
4 Correct 138 ms 484 KB Ok! 1692 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 488 KB Ok! 1653 queries used.
2 Correct 133 ms 484 KB Ok! 1643 queries used.
3 Correct 146 ms 500 KB Ok! 1832 queries used.
4 Correct 127 ms 480 KB Ok! 1602 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 157 ms 468 KB Too many queries! 1913 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

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