oj.uz

Submission #543019

# Submission time Handle Problem Language Result Execution time Memory
543019 2022-03-28T20:37:13 Z MilosMilutinovic Mechanical Doll (IOI18_doll) C++14
100 / 100
 884 ms 14104 KB 
//implementation idea by TadijaSebez
#include "doll.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=200050;
const int M=2*N;
int n,d,root,ls[M],rs[M],tsz,id[M],p[M];
bool was[M];
int val(int x){
	x--;
	int ret=0;
	for(int i=0;i<25;i++)if(x>>i&1)ret+=(1<<(25-i));
	return ret;
}
void Build(int&c,int ss,int se){
	if(se<=d){c=root;return;}
	if(ss==se){c=-id[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);
	n=A.size();
	int sz=1;
	while(sz<n)sz*=2;
	d=sz-n;
	vector<int> ids;
	for(int i=1;i<=sz;i++)ids.pb(i);
	sort(ids.begin(),ids.end(),[&](int i,int j){return val(i)<val(j);});
	for(int i=d;i<sz;i++)was[ids[i]]=true,p[ids[i]]=i+1;
	for(int i=1,ptr=0;i<=sz;i++)if(was[i])id[p[i]]=A[ptr++];
	Build(root,1,sz);
	vector<int> C,X,Y;
	for(int i=0;i<=M;i++)C.pb(-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 'void Build(int&, int, int)':
doll.cpp:20:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |  int mid=ss+se>>1;
      |          ~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 369 ms 5700 KB Output is correct
3 Correct 405 ms 5312 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 9 ms 1612 KB Output is correct
6 Correct 418 ms 6980 KB Output is correct
7 Correct 0 ms 340 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 369 ms 5700 KB Output is correct
3 Correct 405 ms 5312 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 9 ms 1612 KB Output is correct
6 Correct 418 ms 6980 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 829 ms 10208 KB Output is correct
9 Correct 855 ms 10472 KB Output is correct
10 Correct 863 ms 14104 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 369 ms 5700 KB Output is correct
3 Correct 405 ms 5312 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 9 ms 1612 KB Output is correct
6 Correct 418 ms 6980 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 829 ms 10208 KB Output is correct
9 Correct 855 ms 10472 KB Output is correct
10 Correct 863 ms 14104 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 856 ms 13968 KB Output is correct
15 Correct 800 ms 10212 KB Output is correct
16 Correct 844 ms 13808 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 316 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 829 ms 14096 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 312 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 827 ms 8312 KB Output is correct
3 Correct 794 ms 8180 KB Output is correct
4 Correct 827 ms 11228 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 827 ms 8312 KB Output is correct
3 Correct 794 ms 8180 KB Output is correct
4 Correct 827 ms 11228 KB Output is correct
5 Correct 830 ms 12216 KB Output is correct
6 Correct 841 ms 11480 KB Output is correct
7 Correct 867 ms 11616 KB Output is correct
8 Correct 870 ms 11612 KB Output is correct
9 Correct 815 ms 8300 KB Output is correct
10 Correct 825 ms 11352 KB Output is correct
11 Correct 848 ms 11224 KB Output is correct
12 Correct 844 ms 8296 KB Output is correct
13 Correct 816 ms 8904 KB Output is correct
14 Correct 817 ms 8572 KB Output is correct
15 Correct 812 ms 8584 KB Output is correct
16 Correct 18 ms 676 KB Output is correct
17 Correct 391 ms 8756 KB Output is correct
18 Correct 824 ms 9332 KB Output is correct
19 Correct 814 ms 9232 KB Output is correct
20 Correct 843 ms 12988 KB Output is correct
21 Correct 818 ms 12688 KB Output is correct
22 Correct 884 ms 12696 KB Output is correct