oj.uz

Submission #582519

# Submission time Handle Problem Language Result Execution time Memory
582519 2022-06-24T03:01:52 Z 8e7 Mechanical Doll (IOI18_doll) C++17
100 / 100
 158 ms 18944 KB 
#include "doll.h"
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> pos[maxn];
int rx[4*maxn], ry[4*maxn];
int cur;
void build(int ind, vector<int> v) {
	
	if (v.size() <= 2) {
		if (v.size() == 1) {
			rx[-ind] = ind;	
			ry[-ind] = v[0];	
		} else {
			rx[-ind] = v[0];
			ry[-ind] = v[1];
		}
	} else {
		vector<int> l, r;
		for (int i = 0;i < v.size();i++) {
			if (i < (v.size() + 1) / 2) l.push_back(v[i]);
			else r.push_back(v[i]);
		}
		int neg = 1;
		for (int i:l) {
			if (i != -1) {
				neg = 0;
				break;
			}
		}
		if (neg) {
			rx[-ind] = -1;
		} else {
			rx[-ind] = --cur;
			build(cur, l);
		}
		ry[-ind] = --cur;
		build(cur, r);
	}
}
void create_circuit(int M, std::vector<int> A) {
	int N = A.size();
	A.push_back(0);
	for (int i = 0;i < N;i++) {
		pos[A[i]].push_back(i);
	}
	cur = -1;
	
	std::vector<int> C(M + 1);
	C[0] = A[0];

	int b = 0;
	while ((1<<b) < N) b++;

	vector<int> ini(1<<b, -1);
	vector<pii> v;
	for (int i = (1<<b) - N;i < (1<<b);i++) {
		int rev = 0;
		for (int j = 0;j < b;j++) {
			rev += (1<<(b-j-1)) * ((i>>j)&1);
		}
		v.push_back({rev, i});
	}
	sort(v.begin(), v.end());	
	for (int i = 0;i < N;i++) {
		ini[v[i].ss] = A[i+1];
	}

	for (int i = 1; i <= M; ++i) C[i] = -1;	
	build(-1, ini);	
	int S = -cur;
	std::vector<int> X(S), Y(S);
	for (int k = 1; k <= S; ++k) {
		X[k-1] = rx[k], Y[k-1] = ry[k];
	}
	pary(C.begin(), C.end());
	pary(X.begin(), X.end());
	pary(Y.begin(), Y.end());
	answer(C, X, Y);
}
/*
4 4
1 2 1 3
*/

Compilation message

doll.cpp: In function 'void build(int, std::vector<int>)':
doll.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for (int i = 0;i < v.size();i++) {
      |                  ~~^~~~~~~~~~
doll.cpp:38:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |    if (i < (v.size() + 1) / 2) l.push_back(v[i]);
      |        ~~^~~~~~~~~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
doll.cpp:93:2: note: in expansion of macro 'pary'
   93 |  pary(C.begin(), C.end());
      |  ^~~~
doll.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
doll.cpp:94:2: note: in expansion of macro 'pary'
   94 |  pary(X.begin(), X.end());
      |  ^~~~
doll.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
doll.cpp:95:2: note: in expansion of macro 'pary'
   95 |  pary(Y.begin(), Y.end());
      |  ^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2556 KB Output is correct
2 Correct 58 ms 9924 KB Output is correct
3 Correct 47 ms 9672 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 10 ms 3796 KB Output is correct
6 Correct 75 ms 12916 KB Output is correct
7 Correct 2 ms 2656 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2556 KB Output is correct
2 Correct 58 ms 9924 KB Output is correct
3 Correct 47 ms 9672 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 10 ms 3796 KB Output is correct
6 Correct 75 ms 12916 KB Output is correct
7 Correct 2 ms 2656 KB Output is correct
8 Correct 107 ms 13672 KB Output is correct
9 Correct 94 ms 14932 KB Output is correct
10 Correct 145 ms 18944 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2556 KB Output is correct
2 Correct 58 ms 9924 KB Output is correct
3 Correct 47 ms 9672 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 10 ms 3796 KB Output is correct
6 Correct 75 ms 12916 KB Output is correct
7 Correct 2 ms 2656 KB Output is correct
8 Correct 107 ms 13672 KB Output is correct
9 Correct 94 ms 14932 KB Output is correct
10 Correct 145 ms 18944 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 131 ms 17816 KB Output is correct
15 Correct 90 ms 12880 KB Output is correct
16 Correct 136 ms 17260 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2652 KB Output is correct
19 Correct 2 ms 2644 KB Output is correct
20 Correct 142 ms 18352 KB Output is correct
21 Correct 2 ms 2644 KB Output is correct
22 Correct 2 ms 2644 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 80 ms 10776 KB Output is correct
3 Correct 70 ms 11296 KB Output is correct
4 Correct 114 ms 13996 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 80 ms 10776 KB Output is correct
3 Correct 70 ms 11296 KB Output is correct
4 Correct 114 ms 13996 KB Output is correct
5 Correct 158 ms 16424 KB Output is correct
6 Correct 125 ms 15388 KB Output is correct
7 Correct 136 ms 16188 KB Output is correct
8 Correct 123 ms 15160 KB Output is correct
9 Correct 83 ms 11396 KB Output is correct
10 Correct 126 ms 14832 KB Output is correct
11 Correct 108 ms 14880 KB Output is correct
12 Correct 70 ms 11972 KB Output is correct
13 Correct 88 ms 11336 KB Output is correct
14 Correct 83 ms 12296 KB Output is correct
15 Correct 87 ms 12448 KB Output is correct
16 Correct 4 ms 2900 KB Output is correct
17 Correct 89 ms 10724 KB Output is correct
18 Correct 70 ms 10232 KB Output is correct
19 Correct 81 ms 11728 KB Output is correct
20 Correct 114 ms 14572 KB Output is correct
21 Correct 124 ms 14644 KB Output is correct
22 Correct 110 ms 14332 KB Output is correct