Submission #566129

#	Time	Username	Problem	Language	Result	Execution time	Memory
566129		piOOE	ICC (CEOI16_icc)	C++17	0 / 100	5 ms	468 KiB

icc

#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(n);
            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: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10