oj.uz

Submission #421456

# Submission time Handle Problem Language Result Execution time Memory
421456 2021-06-09T07:43:08 Z Jasiekstrz Mechanical Doll (IOI18_doll) C++17
100 / 100
 197 ms 10212 KB 
#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> X(1),Y(1);
vector<int> AA;
int nxt=-2;
void build_tree(int id,int pot,int l,int r);
int try_add(int l,int r,int pot)
{
	//cerr<<"try "<<l<<" "<<r<<" "<<pot<<"\n\n";
	if(r<l)
		return -1;
	if(pot==0)
		return AA[l];
	X.push_back(0);
	Y.push_back(0);
	int id=nxt;
	nxt--;
	build_tree(id,pot,l,r);
	return id;
}
void build_tree(int id,int pot,int l,int r)
{
	int i=-id-1;
	//cerr<<id<<" "<<i<<" "<<pot<<" "<<l<<" "<<r<<"\n";
	//for(int j=l;j<=r;j++)
	//	cerr<<AA[j]<<" ";
	//cerr<<"\n\n";
	vector<int> B[2];
	int j=l;
	for(int it=0;it<2*pot;it++)
	{
		if(it%2==1 || it/2>=2*pot-(r-l+1))
			B[it%2].push_back(AA[j++]);
	}
	int mid=l+(int)B[0].size()-1;
	for(j=0;j<B[0].size();j++)
		AA[l+j]=B[0][j];
	for(j=0;j<B[1].size();j++)
		AA[mid+1+j]=B[1][j];
	int xd=try_add(l,mid,pot/2);
	X[i]=xd;
	xd=try_add(mid+1,r,pot/2);
	Y[i]=xd;
	return;
}
void create_circuit(int M,vector<int> A)
{
	if(A.size()==1)
	{
		vector<int> ans0(M+1);
		ans0[0]=A[0];
		for(int i=1;i<=M;i++)
			ans0[i]=0;
		answer(ans0,vector<int>(0),vector<int>(0));
		return;
	}
	vector<int> C(M+1);
	C[0]=A[0];
	for(int i=1;i<=M;i++)
		C[i]=-1;
	for(int i=0;i<A.size()-1;i++)
		A[i]=A[i+1];
	A.back()=0;
	int pot=1;
	for(pot=1;2*pot<A.size();pot*=2);
	AA=A;
	build_tree(-1,pot,0,A.size()-1);
	vector<bool> st(X.size());
	for(auto v:A)
	{
		int x=-1;
		while(true)
		{
			int *e;
			if(st[-x-1])
				e=&(Y[-x-1]);
			else
				e=&(X[-x-1]);
			st[-x-1]=!st[-x-1];
			if(*e>=0)
			{
				(*e)=v;
				break;
			}
			x=*e;
		}
	}
	//cerr<<"C:\n";
	//for(auto v:C)
	//	cerr<<v<<" ";
	//cerr<<"\n";
	//cerr<<"X,Y:\n";
	//for(auto v:X)
	//	cerr<<v<<" ";
	//cerr<<"\n";
	//for(auto v:Y)
	//	cerr<<v<<" ";
	//cerr<<"\n";
	answer(C,X,Y);
	return;
}

Compilation message

doll.cpp: In function 'void build_tree(int, int, int, int)':
doll.cpp:37:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(j=0;j<B[0].size();j++)
      |          ~^~~~~~~~~~~~
doll.cpp:39:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(j=0;j<B[1].size();j++)
      |          ~^~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:62:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i=0;i<A.size()-1;i++)
      |              ~^~~~~~~~~~~
doll.cpp:66:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for(pot=1;2*pot<A.size();pot*=2);
      |            ~~~~~^~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 60 ms 4304 KB Output is correct
3 Correct 57 ms 4156 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 89 ms 5104 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 60 ms 4304 KB Output is correct
3 Correct 57 ms 4156 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 89 ms 5104 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 112 ms 7116 KB Output is correct
9 Correct 125 ms 8204 KB Output is correct
10 Correct 175 ms 10212 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 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 0 ms 204 KB Output is correct
2 Correct 60 ms 4304 KB Output is correct
3 Correct 57 ms 4156 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 89 ms 5104 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 112 ms 7116 KB Output is correct
9 Correct 125 ms 8204 KB Output is correct
10 Correct 175 ms 10212 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 171 ms 9848 KB Output is correct
15 Correct 108 ms 7640 KB Output is correct
16 Correct 197 ms 9608 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 174 ms 9988 KB Output is correct
21 Correct 1 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 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 105 ms 5468 KB Output is correct
3 Correct 107 ms 6088 KB Output is correct
4 Correct 165 ms 7448 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 105 ms 5468 KB Output is correct
3 Correct 107 ms 6088 KB Output is correct
4 Correct 165 ms 7448 KB Output is correct
5 Correct 166 ms 8056 KB Output is correct
6 Correct 179 ms 9444 KB Output is correct
7 Correct 172 ms 9520 KB Output is correct
8 Correct 165 ms 9240 KB Output is correct
9 Correct 107 ms 7020 KB Output is correct
10 Correct 172 ms 9188 KB Output is correct
11 Correct 160 ms 9488 KB Output is correct
12 Correct 106 ms 7196 KB Output is correct
13 Correct 108 ms 6652 KB Output is correct
14 Correct 111 ms 7552 KB Output is correct
15 Correct 110 ms 7700 KB Output is correct
16 Correct 4 ms 460 KB Output is correct
17 Correct 127 ms 6328 KB Output is correct
18 Correct 102 ms 6444 KB Output is correct
19 Correct 105 ms 7184 KB Output is correct
20 Correct 169 ms 9024 KB Output is correct
21 Correct 161 ms 8988 KB Output is correct
22 Correct 177 ms 9000 KB Output is correct