Submission #1244611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244611		erering	ICC (CEOI16_icc)	C++20	0 / 100	1 ms	576 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];
}
vector<int> vec[MAXN];
int Query(vector<int> a,vector<int> b,bool flag){
    if(flag){
        vector<int> c,d;
        for(auto i:a){
            for(auto j:vec[i])c.pb(j);
        }
        for(auto i:b){
            for(auto j:vec[i])d.pb(j);
        }
        a=c; b=d;
    }
    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,bool flag){
    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,flag)){
        c.clear();
        for(int i=0;i<a.size()/2;i++)c.pb(a[i]);
    }
    if(b.size()==1)return start(c,b,flag);
    vector<int> d;
    for(int i=b.size()-1;i>=b.size()/2;i--)d.pb(b[i]);
    if(Query(c,d,flag))return start(c,d,flag);
    d.clear();
    for(int i=0;i<b.size()/2;i++)d.pb(b[i]);
    return start(c,d,flag);
}
void run(int N) {
    for(int i=1;i<=N;i++){
        par[i]=i;
        sz[i]=1;
    }
    std::random_device rd;
    std::mt19937 g(rd());
    for (int built = 0; built < N - 1; ++built) {
        for(int i=1;i<=N;i++)vec[i].clear();
        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;
        int x=1,cnt=0;
        while(x<all.size()){
            x*=2;
            cnt++;
        }
        for(int i=0;i<cnt;i++){
            a.clear(); b.clear();
            for(int j=0;j<all.size();j++){
                if((j<<i)&1)a.pb(all[j]);
                else b.pb(all[j]);
            }
            if(Query(a,b,1))break;
        }
        pair<int,int> ans=start(a,b,1);
        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,0);
        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