Submission #1305078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305078		jahongir	ICC (CEOI16_icc)	C++20	7 / 100	50 ms	620 KiB

icc

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



void run(int N){

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


	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();
			}

			vec.swap(tmp);
		}

		
		int l = 0, r = lft.size()-1;
		while(l < r){
			int mid = (l+r)>>1;

			sza = 0;
			for(int i = l; i <= mid; i++)
				for(auto x : comp[lft[i]])
					A[sza++] = x;

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

			if(res) r = mid;
			else l = mid+1;
		}

		sza = 0;
		for(auto x : comp[lft[l]])
			A[sza++] = x;

		int a = lft[l];
		l = 0, r = rht.size()-1;
		while(l < r){
			int mid = (l+r)>>1;

			szb = 0;
			for(int i = l; i <= mid; i++)
				for(auto x : comp[rht[i]])
					B[szb++] = x;

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

			if(res) r = mid;
			else l = mid+1;
		}

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

		
		l = 0, r = comp[a].size()-1;
		while(l < r){
			int mid = (l+r)>>1;

			sza = 0;
			for(int i = l; i <= mid; i++)
					A[sza++] = comp[a][i];

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

			if(res) r = mid;
			else l = mid+1;
		}

		sza = 1;
		A[0] = comp[a][l];

		l = 0, r = comp[b].size()-1;
		while(l < r){
			int mid = (l+r)>>1;

			szb = 0;
			for(int i = l; i <= mid; i++)
					B[szb++] = comp[b][i];

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

			if(res) r = mid;
			else l = mid+1;
		}

		
		szb = 1;
		B[0] = comp[b][l];

		setRoad(A[0],B[0]);

		for(auto x : comp[b])
			comp[a].push_back(x);
		comp[b].clear();
	}

}

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