제출 #869537

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
869537		velislavgarkov	ICC (CEOI16_icc)	C++14	100 / 100	106 ms	652 KiB

icc

#include "icc.h"
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN=1e2+10;
int n;
int par[MAXN], p[MAXN];
vector <int> v[MAXN];
int subs[2][MAXN], sub_ind[2];
int pref[MAXN], lev[16][MAXN], cnt_lev[16], maxl;
int qa[MAXN], qb[MAXN];
int index_v[MAXN];
bool used[MAXN];
int qabr, qbbr, br;
int root(int x) {
    if (par[x]==x) return x;
    return par[x]=root(par[x]);
}
void add(int ind, int i) {
    for (auto j:v[index_v[i]]) {
        subs[ind][sub_ind[ind]]=j;
        sub_ind[ind]++;
    }
}
/*
int find_middle(int ql, int qr) {
    if (ql+1==qr) return ql;
    int l, r, mid;
    l=ql; r=qr;
    while (l<r) {
        mid=(l+r)/2;
        if ((pref[mid]-pref[ql-1])*2<=pref[qr]-pref[ql-1]) l=mid+1;
        else r=mid;
    }
    return l-1;
}*/
void build_levels(int level, int l, int r) {
    lev[level][cnt_lev[level]]=r-l+1;
    cnt_lev[level]++;
    if (l>=r) return;
    maxl=max(maxl,level);
    int mid=(l+r)/2;
    build_levels(level+1,l,mid);
    build_levels(level+1,mid+1,r);
}
void find_subsets() {
    int level=1, cur_ind;
    for (int i=0;i<12;i++) cnt_lev[i]=0;
    pref[0]=0;
    for (int i=1;i<br;i++) pref[i]=pref[i-1]+v[index_v[i]].size();
    maxl=0;
    build_levels(0,1,br-1);
    while (level<=maxl) {
        cur_ind=1;
        sub_ind[0]=sub_ind[1]=0;
        for (int i=0;i<cnt_lev[level];i++) {
            for (int j=0;j<lev[level][i];j++,cur_ind++) add(i%2,cur_ind);
        }
        if (query(sub_ind[0],sub_ind[1],subs[0],subs[1])) return;
        level++;
    }
    sub_ind[0]=sub_ind[1]=0;
    for (int i=1;i<br;i++) add(i%2,i);
}
int find_vertex(int i, int j) {
    qbbr=sub_ind[j];
    for (int k=0;k<sub_ind[j];k++) qb[k]=subs[j][k];
    int l, r, mid;
    l=0; r=sub_ind[i]-1;
    while (l<r) {
        qabr=0;
        mid=(l+r)/2;
        for (int k=l;k<=mid;k++) {
            qa[qabr]=subs[i][k];
            qabr++;
        }
        if (query(qabr,qbbr,qa,qb)) r=mid;
        else l=mid+1;
    }
    return subs[i][l];
}
void run(int N) {
    n=N;
    for (int i=1;i<=n;i++) par[i]=i;
    int cnt=0;
    while (cnt<n-1) {
        for (int i=1;i<=n;i++) {
            if (!v[i].empty()) v[i].clear();
        }
        for (int i=1;i<=n;i++) {
            p[i]=root(i);
            v[p[i]].push_back(i);
        }
        br=1;
        for (int i=1;i<=n;i++) {
            if (v[i].empty()) continue;
            index_v[br]=i;
            br++;
        }
        random_shuffle(index_v+1,index_v+br);
        find_subsets();
        random_shuffle(subs[0],subs[0]+sub_ind[0]);
        random_shuffle(subs[1],subs[1]+sub_ind[1]);
        
        int ansa=find_vertex(0,1);
        int ansb=find_vertex(1,0);
        setRoad(ansa,ansb);
        par[root(ansa)]=root(ansb);
        cnt++;
    }
}

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