Submission #1244563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244563		erering	ICC (CEOI16_icc)	C++20	0 / 100	507 ms	327680 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
#include <vector>
using namespace std;
#define pb push_back
const int MAXN=100+5;
int par[MAXN],sz[MAXN];
int find(int x){
    return par[x]=(par[x]==x?x:find(par[x]));
}
void merge(int a,int b){
    a=find(a);
    b=find(b);
    if(sz[a]>sz[b])swap(a,b);
    par[a]=b;
    sz[b]+=sz[a];
}
int Query(vector<int> a,vector<int> b){
    int arr[a.size()],arrb[b.size()];
    for(int i=0;i<a.size();i++)arr[i]=a[i];
    for(int i=0;i<b.size();i++)arrb[i]=b[i];
    return query(a.size(),b.size(),arr,arrb);
}
pair<int,int> start(vector<int> a,vector<int> b){
    if(a.size()==1 && b.size()==1)return {a[0],b[0]};
    if(a.size()==1)swap(a,b);
    vector<int> c;
    for(int i=a.size()-1;i>=a.size()/2;i--)c.pb(a[i]);
    if(!Query(c,b)){
        c.clear();
        for(int i=0;i<a.size()/2;i++)c.pb(a[i]);
    }
    if(b.size()==1)return start(c,b);
    vector<int> d;
    for(int i=b.size()-1;i>=b.size()/2;i--)d.pb(b[i]);
    if(Query(c,d))return start(c,d);
    d.clear();
    for(int i=0;i<b.size()/2;i++)d.pb(b[i]);
    return start(c,d);
}
void run(int N) {
    for(int i=1;i<=N;i++){
        par[i]=i;
        sz[i]=1;
    }
    for (int built = 0; built < N - 1; ++built) {
        vector<int> vec[N+1];
        vector<int> all;
        for(int i=1;i<=N;i++){
            if(vec[find(i)].size()==0)all.pb(find(i));
            vec[find(i)].pb(i);
        }
        vector<int> a,b;
        for(int i=0;i<all.size();i++){
            for(auto j:vec[all[i]]){
                all.pb(j);
            }
        }
        while(1) {
            std::random_device rd;
            std::mt19937 g(rd());
            std::shuffle(all.begin(), all.end(), g);
            for(int i=0;i<all.size()/2;i++)a.pb(all[i]);
            for(int i=all.size()/2;i<all.size();i++)b.pb(all[i]);
            if(Query(a,b))break;
        }
        pair<int,int> ans=start(a,b);
        a.clear(); b.clear();
        for(auto i:vec[ans.first])a.pb(i);
        for(auto i:vec[ans.second])b.pb(i);
        ans=start(a,b);
        merge(ans.first,ans.second);
        setRoad(ans.first,ans.second);
    }
}

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