Submission #1289796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289796		gustavo_d	ICC (CEOI16_icc)	C++17	0 / 100	2 ms	580 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 LOG = 7;
const int MAXN = 100;

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

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<(int)a.size(); i++) tmp[i] = a[i] + 1;
        for (int i=0; i<(int)b.size(); i++) tmp2[i] = b[i] + 1;
        return query((int)a.size(), (int)b.size(), 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';
    if (sz(b) == 1) return a[0];
    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];
}

void run(int N) {
    int n = N;
    for (int e=0; e<n-1; e++) {
        vector<int> grpA, grpB;
        for (int b=0; b<LOG; b++) {
            grpA.clear(); grpB.clear();
            for (int i=0; i<n; i++) vis[i] = false;
            for (int i=0; i<n; i++) {
                if (vis[i]) continue;
                comp.clear();
                dfs(i);
                for (int v : comp) {
                    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() {
        int n; cin >> n;
        run(n);
        return 0;
    }
#endif

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