oj.uz

Submission #345690

# Submission time Handle Problem Language Result Execution time Memory
345690 2021-01-07T21:42:40 Z wwdd Mechanical Doll (IOI18_doll) C++14
100 / 100
 156 ms 10040 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef pair<int,ii> ti;

int rev(int n, int nb) {
	int res = 0;
	for(int i=0;i<=nb;i++) {
		if(n&(1<<i)) {
			res |= 1<<(nb-i);
		}
	}
	return res;
}
void create_circuit(int M, std::vector<int> A) {
	int N = A.size();
	std::vector<int> C(M + 1);
	C[0] = -1;
	for (int i = 1; i <= M; ++i) {
		C[i] = -1;
	}
	/*
	std::vector<int> X(N), Y(N);
	for (int k = 0; k < N; ++k) {
		X[k] = Y[k] = A[k];
	}
	*/
	ll lb = 0;
	while((1<<lb) < N+1) {
		lb++;
	}
	vi X[2];
	X[0].assign(lb,-1);
	X[1].assign(lb,-1);
	for(int i=0;i<lb-1;i++) {
		X[0][i] = -(i+2);
	}
	vector<ti> mop;
	int SZ = N+1;
	for(int lev=1;lev<=lb;lev++) {
		int lz = lev;
		int num = 1<<(lb-lz);
		if(SZ >= num) {SZ -= num;
			int rs = X[0].size()-1;
			for(int j=0;j<num-1;j++) {
				X[0].push_back(-1);
				X[1].push_back(-1);
			}
			for(int j=num-1;j>1;j--) {
				X[(j&1)][(j>>1)+rs] = -(j+rs+1);
			}
			if(num > 1) {
				X[1][lev-1] = -(rs+2);
			} else {
				rs = lb-1;
			}
			if(lev == lb) {
				mop.push_back({0,{rs,0}});
				mop.push_back({(1<<(lz-1)),{rs,1}});
			} else {
				for(int j=0;j<num;j++) {
					mop.push_back({(rev(j,lb-lz-1)<<lz)|(1<<(lz-1)),{rs+(num>>1)+(j>>1),j&1}});
				}
			}
		}
	}
	sort(mop.begin(),mop.end());
	for(int i=0;i<mop.size();i++) {
		int sw = mop[i].second.first;
		int sid = mop[i].second.second;
		if(i < A.size()) {
			X[sid][sw] = A[i];
		}
	}
	ii fin = mop.back().second;
	X[fin.second][fin.first] = 0;
	//lol debug output
	answer(C, X[0], X[1]);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:71:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i=0;i<mop.size();i++) {
      |              ~^~~~~~~~~~~
doll.cpp:74:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   if(i < A.size()) {
      |      ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 46 ms 4212 KB Output is correct
3 Correct 40 ms 3828 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 69 ms 5728 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 46 ms 4212 KB Output is correct
3 Correct 40 ms 3828 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 69 ms 5728 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 78 ms 6600 KB Output is correct
9 Correct 79 ms 7024 KB Output is correct
10 Correct 122 ms 10040 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 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 46 ms 4212 KB Output is correct
3 Correct 40 ms 3828 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 69 ms 5728 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 78 ms 6600 KB Output is correct
9 Correct 79 ms 7024 KB Output is correct
10 Correct 122 ms 10040 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 113 ms 9592 KB Output is correct
15 Correct 73 ms 6284 KB Output is correct
16 Correct 123 ms 9468 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 112 ms 9840 KB Output is correct
21 Correct 3 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 2 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 2 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 72 ms 5928 KB Output is correct
3 Correct 66 ms 5948 KB Output is correct
4 Correct 102 ms 8948 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 72 ms 5928 KB Output is correct
3 Correct 66 ms 5948 KB Output is correct
4 Correct 102 ms 8948 KB Output is correct
5 Correct 113 ms 9328 KB Output is correct
6 Correct 156 ms 9056 KB Output is correct
7 Correct 109 ms 9200 KB Output is correct
8 Correct 126 ms 8952 KB Output is correct
9 Correct 72 ms 5872 KB Output is correct
10 Correct 118 ms 8888 KB Output is correct
11 Correct 106 ms 8860 KB Output is correct
12 Correct 68 ms 5856 KB Output is correct
13 Correct 97 ms 6124 KB Output is correct
14 Correct 74 ms 6124 KB Output is correct
15 Correct 70 ms 6168 KB Output is correct
16 Correct 4 ms 556 KB Output is correct
17 Correct 66 ms 5948 KB Output is correct
18 Correct 66 ms 5912 KB Output is correct
19 Correct 91 ms 5956 KB Output is correct
20 Correct 120 ms 8872 KB Output is correct
21 Correct 124 ms 8852 KB Output is correct
22 Correct 104 ms 8868 KB Output is correct