oj.uz

Submission #546426

# Submission time Handle Problem Language Result Execution time Memory
546426 2022-04-07T13:56:10 Z jamezzz Mechanical Doll (IOI18_doll) C++17
100 / 100
 120 ms 44456 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> out[500005];

void create_circuit(int M,vector<int> A){
	int N=A.size();
	
	if(N==1){
		vector<int> C(M+1,0);
		C[0]=A[0];
		answer(C,{},{});
		return;
	}
	
	vector<int> tmp;
	for(int i=0;i<N;++i){
		tmp.push_back(A[i]);
	}
	tmp.push_back(0);
	
	vector<int> C(M+1);
	vector<int> X,Y;
	
	int pw=1;
	while(pw<=tmp.size())pw*=2;
	int extra=pw-tmp.size();
	
	vector<int> ord[22];
	ord[1].push_back(0);
	ord[1].push_back(1);
	
	for(int i=1;i<19;++i){
		for(int j=0;j<ord[i].size();++j){
			ord[i+1].push_back(ord[i][j]);
			ord[i+1].push_back(ord[i][j]+(1<<i));
		}
	}
	
	int lg=31-__builtin_clz(pw);
	vector<bool> head(pw,false);
	for(int i=0;i<extra;++i)head[ord[lg][i]]=true;
	
	reverse(tmp.begin(),tmp.end());
	for(int i=0;i<pw;++i){
		if(head[i])out[M+1].push_back(-1);
		else{
			out[M+1].push_back(tmp.back());
			tmp.pop_back();
		}
	}
	
	int cur=2;
	for(int i=0;i<M+cur;++i){
		if(i<=M)C[i]=-1;
		else{
			if(out[i].size()%2==1){
				int x=out[i].back();
				out[i].pop_back();
				out[i].push_back(-i+M);
				out[i].push_back(x);
			}
			vector<int> l,r;
			for(int j=0;j<out[i].size();++j){
				if(j%2==0)l.push_back(out[i][j]);
				else r.push_back(out[i][j]);
			}
			
			bool same=true;
			for(int j=0;j<l.size()-1;++j){
				if(l[j]!=l[j+1]){
					same=false;
					break;
				}
			}
			
			if(same)X.push_back(l[0]);
			else{
				X.push_back(-cur);
				swap(out[M+cur],l);
				++cur;
			}
			
			same=true;
			for(int j=0;j<r.size()-1;++j){
				if(r[j]!=r[j+1]){
					same=false;
					break;
				}
			}
			
			if(same)Y.push_back(r[0]);
			else{
				Y.push_back(-cur);
				swap(out[M+cur],r);
				++cur;
			}
		}
	}
	
	answer(C,X,Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:27:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  while(pw<=tmp.size())pw*=2;
      |        ~~^~~~~~~~~~~~
doll.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int j=0;j<ord[i].size();++j){
      |               ~^~~~~~~~~~~~~~
doll.cpp:65:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    for(int j=0;j<out[i].size();++j){
      |                ~^~~~~~~~~~~~~~
doll.cpp:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |    for(int j=0;j<l.size()-1;++j){
      |                ~^~~~~~~~~~~
doll.cpp:86:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |    for(int j=0;j<r.size()-1;++j){
      |                ~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17096 KB Output is correct
2 Correct 51 ms 26496 KB Output is correct
3 Correct 49 ms 26612 KB Output is correct
4 Correct 11 ms 17100 KB Output is correct
5 Correct 19 ms 17480 KB Output is correct
6 Correct 69 ms 30680 KB Output is correct
7 Correct 6 ms 12048 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17096 KB Output is correct
2 Correct 51 ms 26496 KB Output is correct
3 Correct 49 ms 26612 KB Output is correct
4 Correct 11 ms 17100 KB Output is correct
5 Correct 19 ms 17480 KB Output is correct
6 Correct 69 ms 30680 KB Output is correct
7 Correct 6 ms 12048 KB Output is correct
8 Correct 83 ms 36064 KB Output is correct
9 Correct 86 ms 36296 KB Output is correct
10 Correct 120 ms 44456 KB Output is correct
11 Correct 12 ms 17156 KB Output is correct
12 Correct 11 ms 17152 KB Output is correct
13 Correct 11 ms 17096 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17096 KB Output is correct
2 Correct 51 ms 26496 KB Output is correct
3 Correct 49 ms 26612 KB Output is correct
4 Correct 11 ms 17100 KB Output is correct
5 Correct 19 ms 17480 KB Output is correct
6 Correct 69 ms 30680 KB Output is correct
7 Correct 6 ms 12048 KB Output is correct
8 Correct 83 ms 36064 KB Output is correct
9 Correct 86 ms 36296 KB Output is correct
10 Correct 120 ms 44456 KB Output is correct
11 Correct 12 ms 17156 KB Output is correct
12 Correct 11 ms 17152 KB Output is correct
13 Correct 11 ms 17096 KB Output is correct
14 Correct 115 ms 43952 KB Output is correct
15 Correct 83 ms 35952 KB Output is correct
16 Correct 116 ms 43500 KB Output is correct
17 Correct 11 ms 17144 KB Output is correct
18 Correct 12 ms 17096 KB Output is correct
19 Correct 11 ms 17096 KB Output is correct
20 Correct 120 ms 44040 KB Output is correct
21 Correct 11 ms 17112 KB Output is correct
22 Correct 11 ms 17152 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 17096 KB Output is correct
2 Correct 11 ms 17096 KB Output is correct
3 Correct 11 ms 17096 KB Output is correct
4 Correct 12 ms 17128 KB Output is correct
5 Correct 11 ms 17096 KB Output is correct
6 Correct 14 ms 17160 KB Output is correct
7 Correct 12 ms 17096 KB Output is correct
8 Correct 14 ms 17132 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17096 KB Output is correct
2 Correct 29 ms 20804 KB Output is correct
3 Correct 32 ms 21364 KB Output is correct
4 Correct 36 ms 22200 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17096 KB Output is correct
2 Correct 29 ms 20804 KB Output is correct
3 Correct 32 ms 21364 KB Output is correct
4 Correct 36 ms 22200 KB Output is correct
5 Correct 114 ms 43204 KB Output is correct
6 Correct 116 ms 42940 KB Output is correct
7 Correct 112 ms 43004 KB Output is correct
8 Correct 111 ms 43048 KB Output is correct
9 Correct 70 ms 32760 KB Output is correct
10 Correct 106 ms 41808 KB Output is correct
11 Correct 108 ms 42868 KB Output is correct
12 Correct 77 ms 35072 KB Output is correct
13 Correct 82 ms 35652 KB Output is correct
14 Correct 79 ms 35700 KB Output is correct
15 Correct 78 ms 35688 KB Output is correct
16 Correct 14 ms 16644 KB Output is correct
17 Correct 79 ms 33612 KB Output is correct
18 Correct 76 ms 34548 KB Output is correct
19 Correct 80 ms 35132 KB Output is correct
20 Correct 109 ms 42928 KB Output is correct
21 Correct 108 ms 42864 KB Output is correct
22 Correct 105 ms 42872 KB Output is correct