oj.uz

Submission #132777

# Submission time Handle Problem Language Result Execution time Memory
132777 2019-07-19T14:20:31 Z TadijaSebez Mechanical Doll (IOI18_doll) C++11
100 / 100
 197 ms 15516 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=200050;
const int M=2*N;
int ls[M],rs[M],root,tsz;
vector<int> Build(vector<int> v)
{
	if(v.size()==1) return v;
	vector<int> u[2];
	for(int i=0;i<v.size();i++) u[i&1].pb(v[i]);
	u[0]=Build(u[0]);
	u[1]=Build(u[1]);
	v.clear();
	for(int i:u[0]) v.pb(i);
	for(int i:u[1]) v.pb(i);
	return v;
}
int n,m,k;
int a[M],pos[M];
bool use[M];
void Build(int &c, int ss, int se)
{
	if(se<=k){ c=root;return;}
	if(ss==se){ c=-a[ss];return;}
	c=++tsz;
	int mid=ss+se>>1;
	Build(ls[c],ss,mid);
	Build(rs[c],mid+1,se);
}
void create_circuit(int M, vector<int> A)
{
	A.pb(0);
	m=M;n=A.size();
	int sz=1;
	while(sz<A.size()) sz<<=1;
	vector<int> v;
	for(int i=1;i<=sz;i++) v.pb(i);
	v=Build(v);
	k=sz-n;
	for(int i=k;i<sz;i++)
	{
		use[v[i]]=1;
		pos[v[i]]=i+1;
	}
	for(int i=1,j=0;i<=sz;i++)
	{
		if(use[i])
		{
			a[pos[i]]=A[j];
			j++;
		}
	}
	Build(root,1,sz);
	vector<int> C,X,Y;
	C.assign(m+1,-1);
	for(int i=1;i<=tsz;i++) X.pb(-ls[i]),Y.pb(-rs[i]);
	answer(C,X,Y);
}

Compilation message

doll.cpp: In function 'std::vector<int> Build(std::vector<int>)':
doll.cpp:12:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(int i=0;i<v.size();i++) u[i&1].pb(v[i]);
      |              ~^~~~~~~~~
doll.cpp: In function 'void Build(int&, int, int)':
doll.cpp:28:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |  int mid=ss+se>>1;
      |          ~~^~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:37:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  while(sz<A.size()) sz<<=1;
      |        ~~^~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 100 ms 6052 KB Output is correct
3 Correct 85 ms 5812 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 86 ms 8508 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 1 ms 332 KB Output is correct
2 Correct 100 ms 6052 KB Output is correct
3 Correct 85 ms 5812 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 86 ms 8508 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 146 ms 9292 KB Output is correct
9 Correct 197 ms 10284 KB Output is correct
10 Correct 165 ms 14852 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 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 332 KB Output is correct
2 Correct 100 ms 6052 KB Output is correct
3 Correct 85 ms 5812 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 86 ms 8508 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 146 ms 9292 KB Output is correct
9 Correct 197 ms 10284 KB Output is correct
10 Correct 165 ms 14852 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 165 ms 14876 KB Output is correct
15 Correct 133 ms 10032 KB Output is correct
16 Correct 175 ms 15516 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 173 ms 14920 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 172 ms 9808 KB Output is correct
3 Correct 131 ms 9796 KB Output is correct
4 Correct 158 ms 13848 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 172 ms 9808 KB Output is correct
3 Correct 131 ms 9796 KB Output is correct
4 Correct 158 ms 13848 KB Output is correct
5 Correct 167 ms 15512 KB Output is correct
6 Correct 160 ms 15384 KB Output is correct
7 Correct 165 ms 15408 KB Output is correct
8 Correct 168 ms 14488 KB Output is correct
9 Correct 130 ms 9792 KB Output is correct
10 Correct 159 ms 14408 KB Output is correct
11 Correct 154 ms 14216 KB Output is correct
12 Correct 138 ms 9804 KB Output is correct
13 Correct 133 ms 9988 KB Output is correct
14 Correct 134 ms 9920 KB Output is correct
15 Correct 132 ms 10020 KB Output is correct
16 Correct 5 ms 640 KB Output is correct
17 Correct 91 ms 8508 KB Output is correct
18 Correct 129 ms 9804 KB Output is correct
19 Correct 138 ms 9812 KB Output is correct
20 Correct 164 ms 14340 KB Output is correct
21 Correct 195 ms 14100 KB Output is correct
22 Correct 153 ms 14352 KB Output is correct