oj.uz

Submission #769059

# Submission time Handle Problem Language Result Execution time Memory
769059 2023-06-29T06:29:41 Z ono_de206 Mechanical Doll (IOI18_doll) C++14
100 / 100
 482 ms 15152 KB 
#include "doll.h"
#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;

void create_circuit(int m, std::vector<int> a) {
	a.pb(0);
	int n = a.size();
	vector<int> C(m + 1, 0), X, Y;
	const int inf = 1e9 + 10;

	while(n & (n - 1)) {
		n++;
	}

	auto get = [&](int k) -> vector<int> {
		vector<int> vec(k);
		iota(all(vec), 0);
		vector<int> pos;
		int l = 0;
		function<void(vector<int>&)> dfs = [&](vector<int> &vec) {
			if(vec.size() == 1) {
				pos.pb(vec[0]);
				return;
			}
			vector<int> L, R;
			for(int i = 0; i < vec.size(); i += 2) {
				L.pb(vec[i]);
				R.pb(vec[i + 1]);
			}
			dfs(L);
			dfs(R);
		};
		dfs(vec);
		return pos;
	};

	vector<int> pos = get(n), nwa(n, inf);
	vector<pair<int, int>> tmp;
	for(int i = n - a.size(); i < n; i++) {
		tmp.eb(pos[i], i);
	}
	sort(all(tmp));
	int l = 0;
	for(auto it : tmp) {
		nwa[it.ff] = a[l++];
	}
	swap(nwa, a);

	function<int(vector<int>&)> solve = [&](vector<int>& vec) {
		if(set<int>(all(vec)).size() == 1) return vec[0];
		vector<int> first, second;
		for(int i = 0; i < (int)vec.size(); i += 2) {
			first.pb(vec[i]);
			second.pb(vec[i + 1]);
		}
		int id1 = solve(first), id2 = solve(second);
		X.pb(id1);
		Y.pb(id2);
		return -(int)X.size();
	};
	C[0] = solve(a);
	for(int i = 1; i < C.size(); i++) {
		C[i] = C[0];
	}
	for(int i = 0; i < X.size(); i++) {
		if(X[i] == inf) X[i] = C[0];
		if(Y[i] == inf) Y[i] = C[0];
	}
	answer(C, X, Y);
}

Compilation message

doll.cpp: In lambda function:
doll.cpp:42:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    for(int i = 0; i < vec.size(); i += 2) {
      |                   ~~^~~~~~~~~~~~
doll.cpp: In lambda function:
doll.cpp:35:7: warning: unused variable 'l' [-Wunused-variable]
   35 |   int l = 0;
      |       ^
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i = 1; i < C.size(); i++) {
      |                 ~~^~~~~~~~~~
doll.cpp:81:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for(int i = 0; i < X.size(); i++) {
      |                 ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 163 ms 7064 KB Output is correct
3 Correct 155 ms 6664 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Correct 232 ms 8656 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 163 ms 7064 KB Output is correct
3 Correct 155 ms 6664 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Correct 232 ms 8656 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 313 ms 11220 KB Output is correct
9 Correct 324 ms 11408 KB Output is correct
10 Correct 482 ms 15152 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 163 ms 7064 KB Output is correct
3 Correct 155 ms 6664 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Correct 232 ms 8656 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 313 ms 11220 KB Output is correct
9 Correct 324 ms 11408 KB Output is correct
10 Correct 482 ms 15152 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 473 ms 13248 KB Output is correct
15 Correct 306 ms 11188 KB Output is correct
16 Correct 444 ms 13376 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 461 ms 14176 KB Output is correct
21 Correct 1 ms 300 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 53 ms 7880 KB Output is correct
3 Correct 59 ms 7860 KB Output is correct
4 Correct 66 ms 9424 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 53 ms 7880 KB Output is correct
3 Correct 59 ms 7860 KB Output is correct
4 Correct 66 ms 9424 KB Output is correct
5 Correct 450 ms 14596 KB Output is correct
6 Correct 435 ms 14376 KB Output is correct
7 Correct 430 ms 14448 KB Output is correct
8 Correct 414 ms 14036 KB Output is correct
9 Correct 103 ms 8620 KB Output is correct
10 Correct 272 ms 12028 KB Output is correct
11 Correct 321 ms 13092 KB Output is correct
12 Correct 197 ms 9092 KB Output is correct
13 Correct 265 ms 9972 KB Output is correct
14 Correct 272 ms 10560 KB Output is correct
15 Correct 286 ms 10696 KB Output is correct
16 Correct 6 ms 596 KB Output is correct
17 Correct 187 ms 8664 KB Output is correct
18 Correct 187 ms 9064 KB Output is correct
19 Correct 198 ms 9136 KB Output is correct
20 Correct 369 ms 14736 KB Output is correct
21 Correct 296 ms 13832 KB Output is correct
22 Correct 312 ms 13880 KB Output is correct