제출 #1289827

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289827		Sofiatpc	ICC (CEOI16_icc)	C++20	100 / 100	75 ms	624 KiB

icc

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "icc.h"

using namespace __gnu_pbds;
using namespace std;

#define sz(v) (int)v.size()
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
const int MAXN = 105;
int p[MAXN], s[MAXN], a[MAXN], b[MAXN];
ordered_set st;

int find(int x){
	if(p[x] == x)return x;
	return p[x] = find(p[x]);
}

void merge(int a, int b){
	a = find(a), b = find(b);
	if(s[a] < s[b])swap(a,b);
	st.erase( b );
	p[b] = a;
	s[a] += s[b];
}

mt19937 mt(7);

void run(int n){
	for(int i = 1; i <= n; i++){
		p[i] = i; s[i] = 1;
		st.insert(i);
	}

	for(int z = 1; z < n; z++){
		int pta, ptb;

		vector<int> bits;
		for(int i = 6; i >= 0; i--)
			if( (sz(st)-1) & (1<<i) ){
				for(int j = i; j >= 0; j--)bits.push_back(j);
				break;
			}

		shuffle(bits.begin(), bits.end(), mt);
		for(int i = 0; i < sz(bits); i++){
			pta = 0, ptb = 0;
			for(int j = 1; j <= n; j++){
				int x = st.order_of_key(find(j));
				if(x & (1<<bits[i])){ a[pta] = j; pta++; }
				else { b[ptb] = j; ptb++; }
			}

			if(pta > 0 && ptb > 0){
				int x = query(pta, ptb, a, b);
				if(x == 1)break;
			}
		}

		int la = 1, ra = pta;
		while(la != ra){
			int mid = (la+ra)/2;
			if( query(mid, ptb, a, b) == 1)ra = mid;
			else la = mid+1;
		}

		int lb = 1, rb = ptb;
		while(lb != rb){
			int mid = (lb+rb)/2;
			if( query(pta, mid, a, b) == 1)rb = mid;
			else lb = mid+1;
		}

		setRoad(a[la-1],b[lb-1]);
		merge(a[la-1], b[lb-1]);
	}
}

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