Submission #606274

#	Time	Username	Problem	Language	Result	Execution time	Memory
606274		Jarif_Rahman	ICC (CEOI16_icc)	C++17	100 / 100	124 ms	616 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

bool Query(vector<int> _A, vector<int> _B){
    int a = _A.size(), b = _B.size();
    int A[a], B[b];
    for(int i = 0; i < a; i++) A[i] = _A[i]+1;
    for(int i = 0; i < b; i++) B[i] = _B[i]+1;
    return query(a, b, A, B);
}

void SetRoad(int a, int b){
    setRoad(a+1, b+1);
}

void run(int n){
    vector<vector<int>> comps(n);

    for(int i = 0; i < n; i++) comps[i].pb(i);

    for(int I = 0; I < n-1; I++){
        int c = comps.size();
        int k = 1, xr = 0;

        while(k <= c-1){
            vector<int> s0, s1;
            for(int i = 0; i < c; i++){
                if(i&k) for(int x: comps[i]) s1.pb(x);
                else for(int x: comps[i]) s0.pb(x);
            }

            if(Query(s0, s1)) xr+=k;
            k*=2;
        }

        vector<int> s;
        for(int i = 0; i < c; i++){
            if((i^xr) < i || (i^xr) >= c) continue;
            s.pb(i);
        }

        int a = 0, b = int(s.size())-1;
        while(a < b){
            int md = (a+b)/2;
            vector<int> s1, s2;
            for(int i = 0; i <= md; i++){
                for(int x: comps[s[i]]) s1.pb(x);
                for(int x: comps[s[i]^xr]) s2.pb(x);
            }

            if(Query(s1, s2)) b = md;
            else a = md+1;
        }

        int A = s[a], B = s[a]^xr;

        a = 0, b = int(comps[B].size())-1;
        while(a < b){
            int md = (a+b)/2;
            vector<int> ss(comps[B].begin(), comps[B].begin()+md+1);
            if(Query(comps[A], ss)) b = md;
            else a = md+1;
        }
        int node_b = comps[B][a];

        a = 0, b = int(comps[A].size())-1;
        while(a < b){
            int md = (a+b)/2;
            vector<int> ss(comps[A].begin(), comps[A].begin()+md+1);
            if(Query(ss, {node_b})) b = md;
            else a = md+1;
        }
        int node_a = comps[A][a];

        SetRoad(node_a, node_b);

        if(comps[A].size() < comps[B].size()) swap(comps[A], comps[B]);
        while(!comps[B].empty()){
            comps[A].pb(comps[B].back());
            comps[B].pop_back();
        }

        comps.erase(comps.begin()+B);
    }
}

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