oj.uz

Submission #794012

# Submission time Handle Problem Language Result Execution time Memory
794012 2023-07-26T08:42:11 Z NothingXD Mechanical Doll (IOI18_doll) C++17
100 / 100
 119 ms 14248 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;
bool mark[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]);
	}
	bool flgl = false;
	bool flgr = false;
	for (auto x: l) if (x != -1) flgl = true;
	for (auto x: r) if (x != -1) flgr = true;
	if (!flgl){
		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 (!flgr){
		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);
	}
}

vector<int> Calc(int l, int r){
//	debug(l, r);
	if (l + 1 == r){
		return vector<int>{l};
	}
	int mid = (l + r) >> 1;
	vector<int> lc = Calc(l, mid);
	vector<int> rc = Calc(mid, r);
	vector<int> ans;
	for (int i = 0; i < lc.size(); i++){
		ans.push_back(lc[i]);
		ans.push_back(rc[i]);
	}
	return ans;
}

void create_circuit(int M, vector<int> A) {
	n = A.size(); m = M;
	for (int i = 1; i <= n; i++){
		a[i] = A[i-1];
		mark[a[i]] = true;
	}
	int sz = n+1;
	while(sz % 2 == 0) sz /= 2;
	int bad = 0;
	while(sz != 1){
		bad++;
		sz = n + bad + 1;
		while(sz % 2 == 0) sz /= 2;
	}
	sz = n + bad + 1;
	a[n+1] = 0;
	res++;
	out[0] = -1;
	vector<int> ptr = Calc(0, sz);
	vector<int> val;
	int idx = 0;
	for (int i = 0; i < sz; i++){
		if (ptr[i] >= bad){
			val.push_back(idx);
			idx++;
		}
		else{
			val.push_back(-1);
		}
	}
	solve(res, res, val);
	for (int i = 1; i <= m; i++){
		if (mark[i]){
			out[i] = -1;
		}
		else{
			out[i] = 0;
		}
	}
	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++){
      |                  ~~^~~~~~~~~~~~
doll.cpp: In function 'std::vector<int> Calc(int, int)':
doll.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for (int i = 0; i < lc.size(); i++){
      |                  ~~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 47 ms 6276 KB Output is correct
3 Correct 48 ms 5780 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 8 ms 1876 KB Output is correct
6 Correct 59 ms 8464 KB Output is correct
7 Correct 0 ms 340 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 47 ms 6276 KB Output is correct
3 Correct 48 ms 5780 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 8 ms 1876 KB Output is correct
6 Correct 59 ms 8464 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 83 ms 10084 KB Output is correct
9 Correct 102 ms 10664 KB Output is correct
10 Correct 110 ms 14248 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 47 ms 6276 KB Output is correct
3 Correct 48 ms 5780 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 8 ms 1876 KB Output is correct
6 Correct 59 ms 8464 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 83 ms 10084 KB Output is correct
9 Correct 102 ms 10664 KB Output is correct
10 Correct 110 ms 14248 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 118 ms 13700 KB Output is correct
15 Correct 88 ms 9936 KB Output is correct
16 Correct 106 ms 13512 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 119 ms 14084 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 340 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 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 80 ms 10024 KB Output is correct
3 Correct 80 ms 9932 KB Output is correct
4 Correct 102 ms 12528 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 80 ms 10024 KB Output is correct
3 Correct 80 ms 9932 KB Output is correct
4 Correct 102 ms 12528 KB Output is correct
5 Correct 105 ms 13524 KB Output is correct
6 Correct 107 ms 13404 KB Output is correct
7 Correct 107 ms 13396 KB Output is correct
8 Correct 106 ms 12624 KB Output is correct
9 Correct 79 ms 9880 KB Output is correct
10 Correct 104 ms 12488 KB Output is correct
11 Correct 102 ms 12520 KB Output is correct
12 Correct 80 ms 9956 KB Output is correct
13 Correct 89 ms 9912 KB Output is correct
14 Correct 81 ms 9908 KB Output is correct
15 Correct 81 ms 9960 KB Output is correct
16 Correct 3 ms 724 KB Output is correct
17 Correct 62 ms 8280 KB Output is correct
18 Correct 80 ms 9928 KB Output is correct
19 Correct 79 ms 9988 KB Output is correct
20 Correct 118 ms 12444 KB Output is correct
21 Correct 108 ms 12436 KB Output is correct
22 Correct 102 ms 12520 KB Output is correct