oj.uz

답안 #229295

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
229295 2020-05-04T06:39:07 Z islingr CEOI16_icc (CEOI16_icc) C++14
100 / 100
 148 ms 712 KB 
#include "icc.h"
#include <cassert>
#include <iostream>
#include <vector>

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)

#define eb(x...) emplace_back(x)
#define sz(x) int((x).size())
#define trav(x, v) for (auto &x : v)
#define all(x) begin(x), end(x)

#define ff first
#define ss second

using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;

vector<vi> comp;

bool query(vi a, vi b) {
	if (a.empty() || b.empty()) return false;
	return query(sz(a), sz(b), a.data(), b.data());
}

bool query_comp(vi a, vi b) {
	vi x, y;
	trav(c, a) trav(v, comp[c]) x.eb(v);
	trav(c, b) trav(v, comp[c]) y.eb(v);
	return query(x, y);
}

void merge(int a, int b) {
	copy(all(comp[b]), back_inserter(comp[a]));
	comp.erase(begin(comp) + b);
}

pii dnc(vi a, vi b) {
	if (sz(a) < sz(b)) swap(a, b); // sz(b) <= sz(a)
	if (sz(a) == 1 && sz(b) == 1) return {a[0], b[0]};
	int half = (sz(a) + 1)/ 2;
	vi l(begin(a), begin(a) + half), r(begin(a) + half, end(a));
	assert(!l.empty() && !r.empty());
	if (query(l, b)) return dnc(l, b);
	else return dnc(r, b);
}

void run(int n) {
	rep(i, 0, n) comp.eb(vi{i + 1});
	rep(i, 1, n) {
		int l = 0, r = 1;
		if (sz(comp) > 2) {
			int axb = 0;

			for (int j = 0; (1 << j) <= sz(comp); ++j) {
				vi a, b;
				rep(k, 0, sz(comp))
					if (k & 1 << j) a.eb(k);
					else b.eb(k);
				if (query_comp(a, b))
					axb |= 1 << j;
			}
			
			int x; for (x = 0; ~axb & 1 << x; ++x);
			l = 1 << x, r = 0;
			for (int j = 0; (1 << j) <= sz(comp); ++j) {
				if (j == x) continue;
				if (axb & 1 << j) {
					vi a, b;
					rep(k, 0, sz(comp))
						if (k & 1 << x) { if (k & 1 << j) a.eb(k); }
						else { if (~k & 1 << j) b.eb(k); }
					if (query_comp(a, b)) l |= 1 << j;
					else r |= 1 << j;
				} else {
					vi a, b;
					rep(k, 0, sz(comp))
						if (k & 1 << j) {
							if (k & 1 << x) a.eb(k);
							else b.eb(k);
						}
					if (query_comp(a, b)) {
						l |= 1 << j;
						r |= 1 << j;
					}
				}
			}
		}

		auto p = dnc(comp[l], comp[r]);
		merge(l, r);
		setRoad(p.ff, p.ss);
	}
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 512 KB Ok! 113 queries used.
2 Correct 13 ms 512 KB Ok! 110 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 512 KB Ok! 640 queries used.
2 Correct 37 ms 512 KB Ok! 459 queries used.
3 Correct 38 ms 512 KB Ok! 493 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 632 KB Ok! 1523 queries used.
2 Correct 112 ms 512 KB Ok! 1113 queries used.
3 Correct 140 ms 512 KB Ok! 1535 queries used.
4 Correct 148 ms 632 KB Ok! 1503 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 134 ms 512 KB Ok! 1470 queries used.
2 Correct 138 ms 512 KB Ok! 1431 queries used.
3 Correct 128 ms 632 KB Ok! 1310 queries used.
4 Correct 144 ms 512 KB Ok! 1540 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 632 KB Ok! 1327 queries used.
2 Correct 127 ms 512 KB Ok! 1279 queries used.
3 Correct 127 ms 632 KB Ok! 1232 queries used.
4 Correct 127 ms 512 KB Ok! 1412 queries used.
5 Correct 140 ms 712 KB Ok! 1524 queries used.
6 Correct 133 ms 572 KB Ok! 1460 queries used.

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 632 KB Ok! 1449 queries used.
2 Correct 119 ms 568 KB Ok! 1132 queries used.