oj.uz

Submission #242901

# Submission time Handle Problem Language Result Execution time Memory
242901 2020-06-29T17:33:13 Z tonowak ICC (CEOI16_icc) C++14
61 / 100
 244 ms 760 KB 
#include <bits/stdc++.h> // Tomasz Nowak
#include "icc.h"
using namespace std;     // XIII LO Szczecin
using LL = long long;    // Poland
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
template<class T> int size(T &&x) {
	return int(x.size());
}
template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		out << *it << (it == prev(x.end()) ? "" : ", ");
	return out << '}';
}
void dump() {}
template<class T, class... Args> void dump(T &&x, Args... args) {
	cerr << x << ";  ";
	dump(args...);
}
#ifdef DEBUG
  struct Nl{~Nl(){cerr << '\n';}};
# define debug(x...) cerr << (strcmp(#x, "") ? #x ":  " : ""), dump(x), Nl(), cerr << ""
#else
# define debug(...) 0 && cerr
#endif
mt19937_64 rng(0);
int rd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}
// end of templates

int query(vector<int> a, vector<int> b) {
	int ta[size(a)], tb[size(b)];
	REP(i, size(a))
		ta[i] = a[i] + 1;
	REP(i, size(b))
		tb[i] = b[i] + 1;
	return query(size(a), size(b), ta, tb);
}

vector<int> collapse(vector<vector<int>> v) {
	vector<int> ret;
	for(auto &vec : v)
		for(int x : vec)
			ret.emplace_back(x);
	return ret;
}

int query(vector<vector<int>> a, vector<vector<int>> b) {
	return query(collapse(a), collapse(b));
}

template<class T>
pair<T, T> split_half(T a) {
	T left, right;
	REP(i, size(a))
		if(i % 2)
			right.emplace_back(a[i]);
		else
			left.emplace_back(a[i]);
	return {left, right};
}

template<class T>
T find(T a, T b) {
	while(size(a) != 1 or size(b) != 1) {
		debug(a, b);
		if(size(a) < size(b))
			swap(a, b);
		auto [left, right] = split_half(a);
		if(query(left, b))
			a = left;
		else
			a = right;
	}
	return {a[0], b[0]};
}

vector<int> find(vector<vector<int>> a) {
	while(true) {
		shuffle(a.begin(), a.end(), rng);
		auto [left, right] = split_half(a);
		debug(left, right);
		if(query(left, right))
			return find(collapse(left), collapse(right));
	}
}

void run(int n) {
	vector<int> lead(n);
	iota(lead.begin(), lead.end(), 0);

	function<int (int)> find_leader = [&](int v) {
		if(v == lead[v])
			return v;
		return lead[v] = find_leader(lead[v]);
	};

	REP(edge, n - 1) {
		vector<vector<int>> in_lead(n);
		REP(v, n)
			in_lead[find_leader(v)].emplace_back(v);

		vector<vector<int>> components;
		REP(v, n)
			if(lead[v] == v)
				components.emplace_back(in_lead[v]);

		for(auto &v : components)
			shuffle(v.begin(), v.end(), rng);

		auto ret = find(components);
		int v = ret[0],
			u = ret[1];
		debug(v, u);
		setRoad(v + 1, u + 1);
		lead[find_leader(v)] = find_leader(u);
	}
}

Compilation message

icc.cpp: In function 'T find(T, T)':
icc.cpp:74:8: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
   auto [left, right] = split_half(a);
        ^
icc.cpp: In function 'std::vector<int> find(std::vector<std::vector<int> >)':
icc.cpp:86:8: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
   auto [left, right] = split_half(a);
        ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 512 KB Ok! 106 queries used.
2 Correct 11 ms 512 KB Ok! 97 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 512 KB Ok! 526 queries used.
2 Correct 72 ms 512 KB Ok! 817 queries used.
3 Correct 72 ms 632 KB Ok! 784 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 608 KB Ok! 1526 queries used.
2 Correct 244 ms 512 KB Ok! 2093 queries used.
3 Correct 169 ms 760 KB Ok! 1548 queries used.
4 Correct 190 ms 632 KB Ok! 1702 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 640 KB Ok! 1666 queries used.
2 Correct 181 ms 632 KB Ok! 1629 queries used.
3 Correct 218 ms 640 KB Ok! 1852 queries used.
4 Correct 161 ms 512 KB Ok! 1463 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 221 ms 760 KB Too many queries! 1934 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 210 ms 512 KB Too many queries! 1860 out of 1625
2 Halted 0 ms 0 KB -