oj.uz

Submission #882370

# Submission time Handle Problem Language Result Execution time Memory
882370 2023-12-03T05:36:47 Z ono_de206 ICC (CEOI16_icc) C++14
0 / 100
 47 ms 760 KB 
#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);
		}

		bool sus = 0;
		for(int i = 0; i < 10; i++)
		if((1 << i) == (int)all.size())
			sus = 1;
		assert(sus);

		for(int j = 2; j <= sz; j *= 2) {
			int lol = sz / j;
			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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 600 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 604 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 640 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 760 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 600 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 604 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -