oj.uz

Submission #415539

# Submission time Handle Problem Language Result Execution time Memory
415539 2021-06-01T08:25:19 Z Kevin_Zhang_TW Mechanical Doll (IOI18_doll) C++17
100 / 100
 169 ms 10932 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }

#undef KEV

#ifdef KEV 
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010, inf = 1e9;
#include "doll.h"

void create_circuit(int M, std::vector<int> A) {
	int n = A.size(), m = M;
	// C is the place where the ith trigger connect to

	vector<int> C(M + 1), X, Y;

	auto new_s = [&]() {
		int ret = X.size();
		X.pb(0), Y.pb(0);
		return ret;
	};
	
	auto sid = [&](int id) { return - (id+1); };

	DE(n, M);
	int P = inf;

	function<vector<int>(vector<int>)> solve = [&](vector<int> target) {
		int osz = 2, sz = target.size();
		while (osz < sz) osz <<= 1;
		int more = osz - sz;

		vector<int> allid(osz); iota(AI(allid), 0);

		vector<int> val(osz);
		vector<int> ban(osz);

		function<void(int,vector<int>)> gen = [&](int more, vector<int> allid) {
			if (more == 0) return ;
			
			if (more == allid.size()) {
				for (int u : allid) ban[u] = true, val[u] = P;
				return;
			}

			vector<int> L, R;
			for (int i = 0;i < allid.size();++i) {
				(i&1?R:L).pb(allid[i]);
			}

			int sz = L.size(), lm = min(more, sz), rm = more - lm;

			assert(L.size() == R.size());

			if (count(AI(L), osz-1)) swap(lm, rm);
			DE(lm, rm);

			gen(lm, L), gen(rm, R);
		};

		gen(more, allid);

		for (int i = 0, j = 0;i < sz;++i) {
			while (ban[j]) ++j;
			val[j++] = target[i];
			if (i == sz-1) assert(j == osz);
		}

		return val;
	};

	function<int(vector<int>)> create = [&](vector<int> target) {
		if (target.size() == 1) {
			return target[0];
		}
		assert(target.size() % 2 == 0);
		if (count(AI(target), target[0]) == target.size()) {
			return target[0];
		}
		int cur = new_s();
		vector<int> L, R;
		for (int i = 0;i < target.size();++i) {
			(i&1?R:L).pb(target[i]);
		}
		assert(L.size() == R.size());
		int a = create(L), b = create(R);
		X[cur] = a, Y[cur] = b;
		return sid(cur);
	};

	auto spgen = [&](vector<int> target) {
		if (target.size() == 1) return target[0];
		int old = X.size();
		target = solve(target);
		int g = create(target);
		for (int i = old;i < X.size();++i) {
			if (X[i] == P) X[i] = g;
			if (Y[i] == P) Y[i] = g;
		}
		return g;
	};


	C[0] = A[0];

	A.pb(0);

	C[ A[0] ] = spgen(vector<int>(begin(A)+1, end(A)));
	for (int i = 1;i <= m;++i) C[i] = C[A[0]];

	answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:17:17: warning: statement has no effect [-Wunused-value]
   17 | #define DE(...) 0
      |                 ^
doll.cpp:38:2: note: in expansion of macro 'DE'
   38 |  DE(n, M);
      |  ^~
doll.cpp: In lambda function:
doll.cpp:54:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    if (more == allid.size()) {
      |        ~~~~~^~~~~~~~~~~~~~~
doll.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    for (int i = 0;i < allid.size();++i) {
      |                   ~~^~~~~~~~~~~~~~
doll.cpp:17:17: warning: statement has no effect [-Wunused-value]
   17 | #define DE(...) 0
      |                 ^
doll.cpp:69:4: note: in expansion of macro 'DE'
   69 |    DE(lm, rm);
      |    ^~
doll.cpp: In lambda function:
doll.cpp:90:36: warning: comparison of integer expressions of different signedness: 'std::__iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, void>::difference_type' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   if (count(AI(target), target[0]) == target.size()) {
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
doll.cpp:95:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   for (int i = 0;i < target.size();++i) {
      |                  ~~^~~~~~~~~~~~~~~
doll.cpp: In lambda function:
doll.cpp:109:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for (int i = old;i < X.size();++i) {
      |                    ~~^~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:25:6: warning: unused variable 'n' [-Wunused-variable]
   25 |  int n = A.size(), m = M;
      |      ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 53 ms 4056 KB Output is correct
3 Correct 56 ms 5192 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 80 ms 6668 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 53 ms 4056 KB Output is correct
3 Correct 56 ms 5192 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 80 ms 6668 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 98 ms 6808 KB Output is correct
9 Correct 105 ms 9888 KB Output is correct
10 Correct 169 ms 10920 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 53 ms 4056 KB Output is correct
3 Correct 56 ms 5192 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 80 ms 6668 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 98 ms 6808 KB Output is correct
9 Correct 105 ms 9888 KB Output is correct
10 Correct 169 ms 10920 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 167 ms 10776 KB Output is correct
15 Correct 102 ms 9632 KB Output is correct
16 Correct 148 ms 10792 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 2 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 151 ms 10932 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 24 ms 4396 KB Output is correct
3 Correct 29 ms 9544 KB Output is correct
4 Correct 56 ms 10516 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 24 ms 4396 KB Output is correct
3 Correct 29 ms 9544 KB Output is correct
4 Correct 56 ms 10516 KB Output is correct
5 Correct 148 ms 10728 KB Output is correct
6 Correct 139 ms 10684 KB Output is correct
7 Correct 143 ms 10684 KB Output is correct
8 Correct 138 ms 10660 KB Output is correct
9 Correct 79 ms 9536 KB Output is correct
10 Correct 132 ms 10548 KB Output is correct
11 Correct 137 ms 10548 KB Output is correct
12 Correct 95 ms 9544 KB Output is correct
13 Correct 91 ms 5864 KB Output is correct
14 Correct 97 ms 9536 KB Output is correct
15 Correct 96 ms 9584 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 89 ms 7324 KB Output is correct
18 Correct 87 ms 5908 KB Output is correct
19 Correct 133 ms 9504 KB Output is correct
20 Correct 140 ms 10532 KB Output is correct
21 Correct 138 ms 10548 KB Output is correct
22 Correct 138 ms 10540 KB Output is correct