oj.uz

Submission #832415

# Submission time Handle Problem Language Result Execution time Memory
832415 2023-08-21T10:10:50 Z caganyanmaz Mechanical Doll (IOI18_doll) C++17
60.6719 / 100
 54 ms 9836 KB 
#include <bits/stdc++.h>
#define pb push_back
#include "doll.h"
using namespace std;

//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

vector<int> a;
vector<int> x, y;
int n, m;


void create_circuit(int M, vector<int> A) 
{
	a = A;
	if (a.size() == (a.size()&(-a.size())))
		a.pb(0);
	n = a.size();
	int step_count = (a.size()+1)/2;
	int i;
	for (i = 0; i+step_count < a.size(); i++)
	{
		x.pb(a[i]);
		y.pb(a[i+step_count]);
	}
	if (n&1)
	{
		x.pb(a[i]);
		y.pb(0);
	}
	int l = 0, r = x.size();
	int depth = 0;
	while ((r-l) > 1)
	{
		depth++;
		step_count = (r+1 - l)/2;
		for (i = l; i+step_count < r; i++)
		{
			x.pb(-i-1);
			y.pb(-i-step_count-1);
		}
		if (1&(r-l))
		{
			x.pb(-i-1);
			y.pb(0);
		}
		l = r;
		r = x.size();
	}
	int root = -x.size();
	for (int i = 0; i < x.size(); i++)
	{
		if (x[i] == 0)
			x[i] = root;
		if (y[i] == 0)
			y[i] = root;
	}
	int last = root;
	i = x.size()-1;
	int d = 0;
	while (y[i] != root)
	{
		d++;
		i = -y[i]-1;
	}
	y[i] = -x.size()-1;
	int last_encounter = i;
	while (d < depth)
	{
		int xsize = x.size();
		d++;
		x.pb(last);
		y.pb(-xsize-2);
		last_encounter = y.size()-1;
	}
	y[last_encounter] = 0;
	vector<int> c(M+1, root);
	debug(c, x, y);
	answer(c, x, y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:26:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for (i = 0; i+step_count < a.size(); i++)
      |              ~~~~~~~~~~~~~^~~~~~~~~~
doll.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for (int i = 0; i < x.size(); i++)
      |                  ~~^~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
14.7580402392 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 28 ms 6468 KB Output is partially correct
3 Partially correct 29 ms 6424 KB Output is partially correct
4 Partially correct 44 ms 8992 KB Output is partially correct

Subtask #6
45.9139029664 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 28 ms 6468 KB Output is partially correct
3 Partially correct 29 ms 6424 KB Output is partially correct
4 Partially correct 44 ms 8992 KB Output is partially correct
5 Partially correct 50 ms 9836 KB Output is partially correct
6 Partially correct 49 ms 9488 KB Output is partially correct
7 Partially correct 48 ms 9576 KB Output is partially correct
8 Partially correct 46 ms 9260 KB Output is partially correct
9 Partially correct 38 ms 6440 KB Output is partially correct
10 Partially correct 45 ms 9232 KB Output is partially correct
11 Partially correct 47 ms 8916 KB Output is partially correct
12 Partially correct 30 ms 6708 KB Output is partially correct
13 Partially correct 32 ms 7196 KB Output is partially correct
14 Partially correct 32 ms 7300 KB Output is partially correct
15 Partially correct 32 ms 7424 KB Output is partially correct
16 Partially correct 1 ms 468 KB Output is partially correct
17 Correct 37 ms 6048 KB Output is correct
18 Partially correct 32 ms 6672 KB Output is partially correct
19 Partially correct 31 ms 6704 KB Output is partially correct
20 Partially correct 47 ms 9072 KB Output is partially correct
21 Partially correct 54 ms 8980 KB Output is partially correct
22 Partially correct 46 ms 9016 KB Output is partially correct