oj.uz

Submission #771565

# Submission time Handle Problem Language Result Execution time Memory
771565 2023-07-03T06:29:25 Z ttamx Mechanical Doll (IOI18_doll) C++14
25 / 100
 79 ms 12760 KB 
#include "doll.h"
#include<bits/stdc++.h>

using namespace std;

void create_circuit(int m,vector<int> a) {
	int n = a.size();
	vector<int> c(m+1);
	vector<int> lg(n+1);
	for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
	c[0]=a[0];
	vector<int> x,y;
	auto add=[&](int u,int v){
		x.emplace_back(u);
		y.emplace_back(v);
		return -x.size();
	};
	vector<vector<int>> vec(m+1);
	a.emplace_back(0);
	for(int i=0;i<n;i++)vec[a[i]].emplace_back(a[i+1]);
	for(int i=1;i<=m;i++){
		int sz=vec[i].size();
		if(sz==0){
			c[i]=0;
			continue;
		}
		if(sz==1){
			c[i]=vec[i][0];
			continue;
		}
		int lv=lg[sz-1]+1;
		vector<int> res;
		int cnt=1<<(lv-1);
		int tar=-(x.size()+(1<<lv)-1);
		int st=(1<<lv)-sz+1;
		for(int k=1;k<=cnt;k++){
			int u=k;
			int v=k+cnt;
			res.emplace_back(add(u<st?tar:vec[i][u-st],v<st?tar:vec[i][v-st]));
		}
		while(res.size()>1){
			vector<int> tmp;
			for(int i=0;i<res.size();i+=2)tmp.emplace_back(add(res[i],res[i+1]));
			res=tmp;
		}
		c[i]=res[0];
		assert(res[0]==tar);
	}
	answer(c,x,y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:43:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    for(int i=0;i<res.size();i+=2)tmp.emplace_back(add(res[i],res[i+1]));
      |                ~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 19 ms 6608 KB Output is correct
3 Correct 15 ms 5328 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 3796 KB Output is correct
6 Correct 30 ms 8048 KB Output is correct
7 Correct 0 ms 212 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 19 ms 6608 KB Output is correct
3 Correct 15 ms 5328 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 3796 KB Output is correct
6 Correct 30 ms 8048 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 33 ms 7780 KB Output is correct
9 Correct 38 ms 9144 KB Output is correct
10 Correct 56 ms 12100 KB Output is correct
11 Correct 0 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 0 ms 212 KB Output is correct
2 Correct 19 ms 6608 KB Output is correct
3 Correct 15 ms 5328 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 3796 KB Output is correct
6 Correct 30 ms 8048 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 33 ms 7780 KB Output is correct
9 Correct 38 ms 9144 KB Output is correct
10 Correct 56 ms 12100 KB Output is correct
11 Correct 0 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 79 ms 11680 KB Output is correct
15 Correct 34 ms 6480 KB Output is correct
16 Correct 53 ms 9412 KB Output is correct
17 Correct 0 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 59 ms 11440 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Correct 30 ms 6380 KB Output is correct
3 Partially correct 58 ms 8632 KB Output is partially correct
4 Partially correct 52 ms 9652 KB Output is partially correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Correct 30 ms 6380 KB Output is correct
3 Partially correct 58 ms 8632 KB Output is partially correct
4 Partially correct 52 ms 9652 KB Output is partially correct
5 Incorrect 78 ms 12760 KB wrong motion
6 Halted 0 ms 0 KB -