Submission #1289856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289856		gustavo_d	ICC (CEOI16_icc)	C++17	61 / 100	105 ms	640 KiB

icc

// #define LOCAL
#ifndef LOCAL
    #include "icc.h"
#endif
#include <bits/stdc++.h>
using namespace std;

#define sz(v) (int)(v).size()

typedef long long ll;

const int MAXN = 100;

random_device rd;
mt19937 randn(rd());

int tmp[MAXN], tmp2[MAXN];
bool vis[MAXN];
vector<int> adj[MAXN];
vector<int> comp;

#ifdef LOCAL
    void setRoad(int a, int b) {
        cout << "report" << a << ' ' << b << endl;
    };
#endif

int rng(ll l, ll r) {
    return l + (ll)randn() % (r - l + 1);
}

void dfs(int v) {
    comp.push_back(v);
    vis[v] = true;
    for (int viz : adj[v]) {
        if (vis[viz]) continue;
        dfs(viz);
    }
}

int do_query(vector<int> a, vector<int> b) {
    if (sz(a) == 0 or sz(b) == 0) return 0;
    #ifdef LOCAL
        for (int i : a) cout << i << ' ';
        cout << endl;
        for (int i : b) cout << i << ' ';
        cout << endl;
        int v; cin >> v;
        return v;
    #else
        for (int i=0; i<sz(a); i++) tmp[i] = a[i] + 1;
        for (int i=0; i<sz(b); i++) tmp2[i] = b[i] + 1;
        return query(sz(a), sz(b), tmp, tmp2);
    #endif
}

int discoverGrpA(vector<int> a, vector<int> b) {
    int l = 0, r = sz(a)-1; int ans = -1;
    // cout << "descobre:\n";
    // for (int i : a) cout << i << ' ';
    // cout << '\n';
    // for (int i : b) cout << i << ' ';
    // cout << '\n';
    // cout << '\n';
    while (l <= r) {
        int mid = (l + r) / 2;
        vector<int> g;
        for (int i=l; i<=mid; i++) g.push_back(a[i]);
        if (do_query(g, b)) {
            ans = mid;
            r = mid-1;
        } else l = mid+1;
    }
    return a[ans];
}

int hsb(int x) {
    return 31 - __builtin_clz(x);
}

void run(int N) {
    int n = N;
    for (int e=0; e<n-1; e++) {
        for (int i=0; i<n; i++) vis[i] = false;
        vector<vector<int>> comps;
        for (int i=0; i<n; i++) {
            if (vis[i]) continue;
            comp.clear();
            dfs(i);
            comps.push_back(comp);
        }

        vector<int> grpA, grpB;

        int cnt = 0;
        while (true) {
            cnt++;
            grpA.clear(); grpB.clear();
            for (vector<int> comp : comps) {
                if (rng(1, 2) == 1) {
                    for (int v : comp) grpA.push_back(v);
                } else {
                    for (int v : comp) grpB.push_back(v);
                }
            }
            if (sz(grpA) == 0 or sz(grpB) == 0) cnt--;
            if (do_query(grpA, grpB)) break;
        }
        cerr << cnt << endl;

        // int log = hsb(sz(comps)-1) + 1;
        // // assert(log <= 7);
        // int p[log];
        // for (int i=0; i<log; i++) p[i] = i;
        // shuffle(p, p+log, randn);

        // for (int j=0; j<log; j++) {
        //     int b = p[j];
        //     grpA.clear(); grpB.clear();

        //     for (int i=0; i<sz(comps); i++) {
        //         for (int v : comps[i]) {
        //             if ((i & (1 << b)) != 0) grpA.push_back(v);
        //             else grpB.push_back(v);
        //         }
        //     }
        //     if (do_query(grpA, grpB)) break;
        // }
        int u = discoverGrpA(grpA, grpB);
        int v = discoverGrpA(grpB, {u});
        setRoad(u+1, v+1);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

#ifdef LOCAL
    int main() {
        cout << rng(1, 2) << endl;
        int n; cin >> n;
        cout << hsb(n);
        return 0;
        run(n);
        return 0;
    }
#endif

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10