Submission #882345

#	Time	Username	Problem	Language	Result	Execution time	Memory
882345		ono_de206	ICC (CEOI16_icc)	C++14	18 / 100	239 ms	640 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], is[mxn], n;
vector<int> g[mxn], all;

void merge(int x, int 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]));
	is[y] = 0;
	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(int x, int y) {
	pair<int, int> ret{0, 0};
	int A[n + 1], B[n + 1];
	int sza, szb = 0;
	int l = -1, r = (int)g[x].size() - 1;
	for(int p : g[y]) {
		B[szb++] = p;
	}
	while(r - l > 1) {
		int m = (l + r) / 2;
		sza = 0;
		for(int i = 0; i <= m; i++) {
			A[sza++] = g[x][i];
		}
		if(query(sza, szb, A, B)) r = m;
		else l = m;
	}
	ret.ff = g[x][r];

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

void run(int _n) {
	n = _n;
	for(int i = 1; i <= n; i++) {
		g[i].pb(i);
		all.pb(i);
	}
	for(int t = 1; t < n; t++) {
		int x = -1, y = -1;
		vector<int> a, b = all;
		for(int i : all) {
			a.pb(i);
			b.erase(b.begin());
			int tmp = ask(a, b);
			if(tmp == 0 && y == -1 && x != -1) y = i;
			if(tmp == 1 && x == -1) x = i;
		}
		pair<int, int> ans = find(x, y);
		setRoad(ans.ff, ans.ss);
		merge(x, y);
	}
}

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