Submission #1289886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289886		ChuanChen	ICC (CEOI16_icc)	C++20	90 / 100	84 ms	644 KiB

icc

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

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

#define debug(v) cerr << #v << ": " << v << endl;

mt19937 rng(time(NULL));
const int MAXN = 110;
int rep[MAXN], N;
vector<int> comp[MAXN];


int do_query(vector<int> a, vector<int> b) {
    #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
        int tmp[MAXN], tmp2[MAXN];
        for (int i=0; i<(int)a.size(); i++) tmp[i] = a[i];
        for (int i=0; i<(int)b.size(); i++) tmp2[i] = b[i];
        return query((int)a.size(), (int)b.size(), tmp, tmp2);
    #endif
}

pair<int, int> find_aresta(vector<int> A, vector<int> B){
    if(A.size() == B.size() && A.size() == 1) return {A[0], B[0]};
    if(A.size() > B.size()) swap(A, B);
    vector<int> t1, t2;
    for(int i = 0; i < (B.size()+1)/2; i++) t1.push_back(B[i]);
    for(int i = (B.size())/2; i < B.size(); i++) t2.push_back(B[i]);
    int verdic = do_query(A, t1);
    if(verdic == 1) return find_aresta(A, t1);
    else return find_aresta(A, t2);
}

int find(int no){
    if(rep[no] == no) return no;
    return rep[no] = find(rep[no]);
}

void merge(int a, int b){
    a = find(a), b = find(b);
    if(comp[a].size() < comp[b].size()) swap(a, b);//sz[a] > sz[b]
    rep[b] = rep[a];
    for(int i : comp[b]) comp[a].push_back(i);
    comp[b].clear();
}

void solve(int n){
    if(n == 1) return;
    vector<int> comp_no_qst;
    for(int i = 1; i <= N; i++) comp_no_qst.push_back(rep[i]);
    sort(comp_no_qst.begin(), comp_no_qst.end());
    int maxComp = comp_no_qst.back();
    comp_no_qst.erase( unique(comp_no_qst.begin(), comp_no_qst.end()), comp_no_qst.end() );

    for(int k = 0; (1<<k) < maxComp; k++){
        vector<int> A, B;
        for(int c : comp_no_qst){
            if((c-1)&(1<<k)) for(int no : comp[c]) A.push_back(no);
            else for(int no : comp[c]) B.push_back(no);
        }
        int verdic = do_query(A, B);

        if(verdic){
            auto [a, b] = find_aresta(A, B);
            setRoad(a, b);
            merge(a, b);
            break;
        }
    }
    solve(n-1);
}

void run(int n){
    N = n;
    for(int i = 1; i <= n; i++){
        rep[i] = i;
        comp[i].push_back(i);
    }
    solve(n);
}

#ifdef LOCAL
    int main() {
        int n; cin >> n;
        run(n);
        return 0;
    }
#endif

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