Submission #882369

#	Time	Username	Problem	Language	Result	Execution time	Memory
882369		ono_de206	ICC (CEOI16_icc)	C++14	0 / 100	5 ms	860 KiB

icc

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

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

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

//#define int long long

typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int mxn = 110;
int A[mxn], B[mxn], n, par[mxn];
vector<int> g[mxn], all;

int get(int x) {
	if(par[x] == x) return x;
	return par[x] = get(par[x]);
}

void merge(int x, int y) {
	x = get(x);
	y = get(y);
	if(g[x].size() < g[y].size()) swap(x, y);
	all.erase(find(all(all), y));
	g[x].insert(g[x].end(), all(g[y]));
	par[y] = x;
	g[y].clear();
}

int ask(vector<int> a, vector<int> b) {
	int sza = 0, szb = 0;
	for(int x : a) {
		for(int y : g[x]) {
			A[sza++] = y;
		}
	}
	for(int x : b) {
		for(int y : g[x]) {
			B[szb++] = y;
		}
	}
	return query(sza, szb, A, B);
}

pair<int, int> find(vector<int> x, vector<int> y) {
	pair<int, int> ret{0, 0};
	int A[n + 1], B[n + 1];
	int sza, szb = 0;
	int l = -1, r = (int)x.size() - 1;
	for(int p : y) {
		B[szb++] = p;
	}
	while(r - l > 1) {
		int m = (l + r) / 2;
		sza = 0;
		for(int i = 0; i <= m; i++) {
			A[sza++] = x[i];
		}
		if(query(sza, szb, A, B)) r = m;
		else l = m;
	}
	ret.ff = x[r];

	sza = 0;
	l = -1, r = (int)y.size() - 1;
	for(int p : x) {
		A[sza++] = p;
	}
	while(r - l > 1) {
		int m = (l + r) / 2;
		szb = 0;
		for(int i = 0; i <= m; i++) {
			B[szb++] = y[i];
		}
		if(query(sza, szb, A, B)) r = m;
		else l = m;
	}
	ret.ss = y[r];
	return ret;
}

void run(int _n) {
	n = _n;
	for(int i = 1; i <= n; i++) {
		g[i].pb(i);
		all.pb(i);
		par[i] = i;
	}
	for(int t = 1; t < n; t++) {
		int sz = (int)all.size();
		while(sz & (sz - 1)) {
			sz++;
			all.pb(-1);
		}

		for(int j = 2; j <= sz; j *= 2) {
			int lol = sz / j;
			assert(lol % 2 == 0);
			vector<int> a, b;
			for(int k = 1; k <= j; k++) {
				for(int p = lol * (k - 1) + 1; p <= lol * k; p++) {
					if(all[p] != -1) {
						if(k % 2) a.pb(all[p]);
						else b.pb(all[p]);
					}
				}
			}
			if(ask(a, b)) {
				vector<int> aa, bb;
				for(int x : a) {
					aa.insert(aa.end(), all(g[x]));
				}
				for(int x : b) {
					bb.insert(bb.end(), all(g[x]));
				}
				pair<int, int> ans = find(aa, bb);
				setRoad(ans.ff, ans.ss);
				merge(ans.ff, ans.ss);
				break;
			}
		}

		while(all.size() && all.back() == -1) {
			all.pop_back();
		}
	}
}

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