Submission #1305086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305086		jahongir	ICC (CEOI16_icc)	C++20	100 / 100	70 ms	628 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>
using namespace std;


int par[101];

int get(int u){
    if(par[u]<0) return u;
    return par[u]=get(par[u]);
}


void run(int N){

	vector<int> comp[N+1];
	for(int i = 1; i <= N; i++)
		comp[i].push_back(i), par[i] = -1;


	int A[N], B[N], sza, szb;

	for(int _ = 1; _ < N; _++){
		vector<vector<int>> vec(1);

		for(int i = 1; i <= N; i++) if(!comp[i].empty())
			vec[0].push_back(i);

		vector<int> lft,rht;

		for(; ;){
			lft.clear(), rht.clear();

			int cnt = 0;
			for(auto x : vec){
				for(int i = 0; i < (x.size()+cnt)/2; i++)
					lft.push_back(x[i]);
				for(int i = (x.size()+cnt)/2; i < x.size(); i++)
					rht.push_back(x[i]);
				
				cnt ^= 1;
			}

			sza = 0, szb = 0;
			for(auto x : lft)
				for(auto u : comp[x])
					A[sza++] = u;
			for(auto x : rht)
				for(auto u : comp[x])
					B[szb++] = u;

			int res = query(sza,szb,A,B);

			if(res) break;

			vector<vector<int>> tmp;
			cnt = 0;
			for(auto x : vec){
				tmp.push_back({});
				for(int i = 0; i < (x.size()+cnt)/2; i++)
					tmp.back().push_back(x[i]);
				if(tmp.back().size()==1) tmp.pop_back();
				tmp.push_back({});
				for(int i = (x.size()+cnt)/2; i < x.size(); i++)
					tmp.back().push_back(x[i]);
				if(tmp.back().size()==1) tmp.pop_back();
                cnt^=1;
			}

			vec.swap(tmp);
		}


		vector<int> tmp;
        for(auto x : lft)
            for(auto u : comp[x])
                tmp.push_back(u);
        swap(lft,tmp);
        tmp.clear();
        for(auto x : rht)
            for(auto u : comp[x])
                tmp.push_back(u);
        swap(rht,tmp);



        int szb = 0;
        for(auto x : rht)
            B[szb++] = x;

        int l = 0, r = lft.size()-1;
        while(l < r){
            int mid = (l+r)>>1;
            sza = 0;
            for(int i = l; i <= mid; i++)
                A[sza++] = lft[i];
            
            if(query(sza,szb,A,B)) r = mid;
            else l = mid+1;
        }

        int u = lft[l];
        sza = 1, A[0] = u;

        l = 0, r = rht.size()-1;
        while(l < r){
            int mid = (l+r)>>1;
            szb = 0;
            for(int i = l; i <= mid; i++)
                B[szb++] = rht[i];
            
            if(query(sza,szb,A,B)) r = mid;
            else l = mid+1;
        }
        int v = rht[l];

        setRoad(u,v);

        u = get(u), v = get(v);

        if(par[u]>par[v]) swap(u,v);
        par[u] += par[v]; par[v] = u;

        for(auto x : comp[v]) comp[u].push_back(x);
        comp[v].clear();

	}

}

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