oj.uz

Submission #793819

# Submission time Handle Problem Language Result Execution time Memory
793819 2023-07-26T07:01:25 Z NothingXD Mechanical Doll (IOI18_doll) C++17
53 / 100
 137 ms 27704 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;
typedef complex<ld> point;

void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 4e5 + 10;

int n, m, a[maxn], out[maxn], out1[maxn], out2[maxn], res;
vector<int> idx[maxn];

void solve(int v, int root, vector<int> tmp){
	//debug(v);
	//for (auto x: tmp) debug(x);
	vector<int> l;
	vector<int> r;
	for (int i = 0; i < tmp.size(); i++){
		if (i&1) r.push_back(tmp[i]);
		else l.push_back(tmp[i]);
	}
	if (l.back() == -1){
		out1[v-1] = -root;
	}
	else if (l.size() == 1){
		out1[v-1] = a[l[0]+1];
	}
	else{
		res++;
		out1[v-1] = -res;
		solve(res, root, l);
	}
	if (r.back() == -1){
		out2[v-1] = -root;
	}
	else if (r.size() == 1){
		out2[v-1] = a[r[0]+1];
	}
	else{
		res++;
		out2[v-1] = -res;
		solve(res, root, r);
	}
}

void create_circuit(int M, vector<int> A) {
	n = A.size(); m = M;
	for (int i = 0; i < n; i++){
		a[i] = A[i];
		idx[a[i]].push_back(i);
	}
	a[n] = 0;
	out[0] = a[0];
	for (int i = 1; i <= m; i++){
		int tmp = idx[i].size();
		if (tmp == 0){
			out[i] = 0;
			continue;
		
		}
		reverse(all(idx[i]));
		while(tmp % 2 == 0) tmp /= 2;
		while(tmp != 1){
			idx[i].push_back(-1);
			tmp = idx[i].size();
			while(tmp % 2 == 0) tmp /= 2;
		}
		reverse(all(idx[i]));
		int sz = idx[i].size();
		if (sz == 1){
			out[i] = a[idx[i][0]+1];
			continue;
		}
	//	debug(i, idx[i].size());
		res++;
		out[i] = -res;
		solve(res, res, idx[i]);
	}
	vector<int> C(m+1), X(res), Y(res);
	for (int i = 0; i <= m; i++){
		C[i] = out[i];
	//	debug(i, C[i]);
	}
	//debug(res);
	for (int i = 0; i < res; i++){
		X[i] = out1[i];
		Y[i] = out2[i];
	//	debug(-(i+1), X[i], Y[i]);
	}
	answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void solve(int, int, std::vector<int>)':
doll.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (int i = 0; i < tmp.size(); i++){
      |                  ~~^~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 23 ms 14104 KB Output is correct
3 Correct 18 ms 13524 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 15 ms 11220 KB Output is correct
6 Correct 38 ms 15480 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 23 ms 14104 KB Output is correct
3 Correct 18 ms 13524 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 15 ms 11220 KB Output is correct
6 Correct 38 ms 15480 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 40 ms 16424 KB Output is correct
9 Correct 43 ms 16852 KB Output is correct
10 Correct 60 ms 19780 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 4 ms 9684 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 23 ms 14104 KB Output is correct
3 Correct 18 ms 13524 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 15 ms 11220 KB Output is correct
6 Correct 38 ms 15480 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 40 ms 16424 KB Output is correct
9 Correct 43 ms 16852 KB Output is correct
10 Correct 60 ms 19780 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 4 ms 9684 KB Output is correct
14 Correct 83 ms 21376 KB Output is correct
15 Correct 43 ms 15876 KB Output is correct
16 Correct 66 ms 19088 KB Output is correct
17 Correct 4 ms 9684 KB Output is correct
18 Correct 4 ms 9684 KB Output is correct
19 Correct 4 ms 9684 KB Output is correct
20 Correct 84 ms 20460 KB Output is correct
21 Correct 4 ms 9728 KB Output is correct
22 Correct 6 ms 9684 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 9684 KB Output is partially correct
2 Correct 50 ms 16992 KB Output is correct
3 Partially correct 86 ms 23556 KB Output is partially correct
4 Partially correct 100 ms 25564 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 9684 KB Output is partially correct
2 Correct 50 ms 16992 KB Output is correct
3 Partially correct 86 ms 23556 KB Output is partially correct
4 Partially correct 100 ms 25564 KB Output is partially correct
5 Partially correct 107 ms 25068 KB Output is partially correct
6 Partially correct 122 ms 26288 KB Output is partially correct
7 Partially correct 124 ms 25876 KB Output is partially correct
8 Partially correct 133 ms 26956 KB Output is partially correct
9 Partially correct 99 ms 22404 KB Output is partially correct
10 Partially correct 135 ms 27704 KB Output is partially correct
11 Partially correct 137 ms 27680 KB Output is partially correct
12 Partially correct 89 ms 21548 KB Output is partially correct
13 Partially correct 82 ms 20620 KB Output is partially correct
14 Partially correct 92 ms 20296 KB Output is partially correct
15 Partially correct 76 ms 19820 KB Output is partially correct
16 Partially correct 6 ms 10012 KB Output is partially correct
17 Partially correct 74 ms 19308 KB Output is partially correct
18 Partially correct 78 ms 19320 KB Output is partially correct
19 Partially correct 75 ms 19916 KB Output is partially correct
20 Partially correct 94 ms 23336 KB Output is partially correct
21 Partially correct 110 ms 25680 KB Output is partially correct
22 Partially correct 92 ms 22604 KB Output is partially correct