oj.uz

Submission #566125

# Submission time Handle Problem Language Result Execution time Memory
566125 2022-05-21T20:50:54 Z piOOE ICC (CEOI16_icc) C++17
0 / 100
 2000 ms 596 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() && (abs(sz(a) - sz(b)) <= 5) && 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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2084 ms 468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2082 ms 468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2085 ms 468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2072 ms 596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 241 ms 592 KB Too many queries! 2077 out of 1625
2 Halted 0 ms 0 KB -