제출 #1289861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289861		ChuanChen	ICC (CEOI16_icc)	C++20	0 / 100	2 ms	580 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]+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
}

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()/2; i++) t1.push_back(B[i]);
    for(int i = B.size()/2; i < B.size(); i++) t2.push_back(B[i]);
    // cerr << "A: "; for(int i : A) cerr << i << ' '; cerr << endl;
    // cerr << "t1: "; for(int i : t1) cerr << i << ' '; cerr << endl;
    // cerr << "t2: "; for(int i : t2) cerr << i << ' '; cerr << endl;

    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);
    // cerr << "merging " << a << ' ' << b << endl;
    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();
    // cerr << "comp[a]: "; for(int i : comp[a]) cerr << i << ' '; cerr << endl;
}

void solve(int n){
    if(n == 1) return;
    // debug(n);
    // debug(all_n);

    vector<int> comp_no_qst;
    for(int i = 0; i < N; i++) comp_no_qst.push_back(rep[i]);
    // cerr << "comp_no_qst: "; for(int i : comp_no_qst) cerr << i << ' '; cerr << endl;
    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() );

    vector<int> ks;
    for(int k = 0; (1<<k) <= maxComp; k++) ks.push_back(k);
    shuffle(ks.begin(), ks.end(), rng);

    // for(int k = 0;; k++){
    for(int k : ks){
        vector<int> A, B;
        // cerr << "comp_no_qst: "; for(int i : comp_no_qst) cerr << i << ' '; cerr << endl;
        for(int c : comp_no_qst){
            if(c&(1<<k)) for(int no : comp[c]) A.push_back(no);
            else for(int no : comp[c]) B.push_back(no);
        }
        // cerr << "A: "; for(int i : A) cerr << i << ' '; cerr << endl;
        // cerr << "B: "; for(int i : B) cerr << i << ' '; cerr << endl;
        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 = 0; 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: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10