oj.uz

Submission #771742

# Submission time Handle Problem Language Result Execution time Memory
771742 2023-07-03T08:40:48 Z ttamx Mechanical Doll (IOI18_doll) C++14
100 / 100
 154 ms 23724 KB 
#include "doll.h"
#include<bits/stdc++.h>
 
using namespace std;
 
void create_circuit(int m,vector<int> a) {
	int n = a.size();
	a.emplace_back(0);
	vector<int> c(m+1);
	vector<int> x,y;
	int lv=0;
	while((1<<lv)<n)lv++;
	int sz=1<<lv;
	vector<int> t(2<<lv),id(2<<lv,m+1),pos(1<<lv);
	for(int i=0;i<1<<lv;i++)for(int j=0;j<lv;j++)if((i>>j)&1)pos[i]+=1<<(lv-j-1);
	map<int,int> mp;
	for(int i=0;i<n;i++)t[(2<<lv)-1-i]=1,mp[pos[(1<<lv)-i-1]];
	int idx=0;
	for(auto &[x,y]:mp)y=++idx;
	for(int i=0;i<n;i++)id[(2<<lv)-1-i]=a[mp[pos[(1<<lv)-i-1]]];
	int cnt=0;
	for(int i=(1<<lv)-1;i>=1;i--){
		t[i]=t[i*2]+t[i*2+1];
		if(t[i]){
			x.emplace_back(id[i*2]);
			y.emplace_back(id[i*2+1]);
			id[i]=-x.size();
		}
	}
	for(auto &i:x)if(i>m)i=id[1];
	for(auto &i:y)if(i>m)i=id[1];
	c[0]=a[0];
	for(int i=1;i<=m;i++)c[i]=id[1];
	answer(c,x,y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:19:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |  for(auto &[x,y]:mp)y=++idx;
      |            ^
doll.cpp:13:6: warning: unused variable 'sz' [-Wunused-variable]
   13 |  int sz=1<<lv;
      |      ^~
doll.cpp:21:6: warning: unused variable 'cnt' [-Wunused-variable]
   21 |  int cnt=0;
      |      ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 42 ms 8392 KB Output is correct
3 Correct 43 ms 9484 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 65 ms 12676 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 42 ms 8392 KB Output is correct
3 Correct 43 ms 9484 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 65 ms 12676 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 77 ms 14792 KB Output is correct
9 Correct 89 ms 17792 KB Output is correct
10 Correct 134 ms 23724 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 42 ms 8392 KB Output is correct
3 Correct 43 ms 9484 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 65 ms 12676 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 77 ms 14792 KB Output is correct
9 Correct 89 ms 17792 KB Output is correct
10 Correct 134 ms 23724 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 130 ms 23324 KB Output is correct
15 Correct 82 ms 16928 KB Output is correct
16 Correct 141 ms 23256 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 142 ms 23432 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 296 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 0 ms 300 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 212 KB Output is correct
2 Correct 69 ms 14344 KB Output is correct
3 Correct 78 ms 16616 KB Output is correct
4 Correct 122 ms 22464 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 69 ms 14344 KB Output is correct
3 Correct 78 ms 16616 KB Output is correct
4 Correct 122 ms 22464 KB Output is correct
5 Correct 134 ms 22956 KB Output is correct
6 Correct 129 ms 22844 KB Output is correct
7 Correct 142 ms 22976 KB Output is correct
8 Correct 136 ms 22628 KB Output is correct
9 Correct 77 ms 16540 KB Output is correct
10 Correct 154 ms 22556 KB Output is correct
11 Correct 124 ms 22552 KB Output is correct
12 Correct 94 ms 16628 KB Output is correct
13 Correct 72 ms 14364 KB Output is correct
14 Correct 82 ms 16756 KB Output is correct
15 Correct 82 ms 16904 KB Output is correct
16 Correct 3 ms 852 KB Output is correct
17 Correct 73 ms 14340 KB Output is correct
18 Correct 71 ms 14320 KB Output is correct
19 Correct 94 ms 16516 KB Output is correct
20 Correct 120 ms 22608 KB Output is correct
21 Correct 127 ms 22560 KB Output is correct
22 Correct 124 ms 22524 KB Output is correct