oj.uz

Submission #1074143

# Submission time Handle Problem Language Result Execution time Memory
1074143 2024-08-25T08:20:10 Z Elias Mechanical Doll (IOI18_doll) C++17
39 / 100
 99 ms 15344 KB 
#include <bits/stdc++.h>

using namespace std;

#ifndef _DEBUG
#include "doll.h"
#else
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
#endif

vector<int> x;
vector<int> y;
vector<int> a;

int max_levels = 0;

int construct_recursive(int i, int level, int index)
{
	while (x.size() <= index)
	{
		x.push_back(0);
		y.push_back(0);
	}
	if (level < max_levels)
	{
		x[index] = -construct_recursive(i, level + 1, index * 2 + 1) - 1;
		y[index] = -construct_recursive(i + (1 << level), level + 1, index * 2 + 2) - 1;
	}
	else
	{
		if (i >= a.size())
		{
			x[index] = -1;
		}
		else
		{
			x[index] = a[i];
		}

		if (i + (1 << level) >= a.size())
		{
			if (i == (1 << level) - 1)
			{
				y[index] = 0;
			}
			else
			{
				y[index] = -1;
			}
		}
		else
		{
			y[index] = a[i + (1 << level)];
		}
	}
	return index;
}

void create_circuit(int M, std::vector<int> A)
{
	x = y = a = vector<int>();

	vector<int> c(M + 1, -1);

	unordered_map<int, int> counts;

	for (int x : A) {
		counts[x]++;
	}

	vector<int> keep(A.size(), 1);

	for (int i = 0; i < A.size() - 1; i++) {
		if (counts[A[i]] == 1) {
			keep[i + 1] = 0;
			c[A[i]] = A[i + 1];
		}
	}

	for (int i = 0; i < A.size(); i++) {
		if (keep[i]) {
			a.push_back(A[i]);
		}
	}

	int n = a.size();

	int number_of_options = 2;
	while (number_of_options < n + 1) {
		max_levels++;
		number_of_options *= 2;
	}

	c[0] = -construct_recursive(0, 0, 0) - 1;

	// assert(false);

	answer(c, x, y);
}

#ifdef _DEBUG

namespace
{

	constexpr int P_MAX = 20000000;
	constexpr int S_MAX = 400000;

	int M, N;
	std::vector<int> A;

	bool answered;
	int S;
	std::vector<int> IC, IX, IY;

	int read_int()
	{
		int x;
		if (scanf("%d", &x) != 1)
		{
			fprintf(stderr, "Error while reading input\n");
			exit(1);
		}
		return x;
	}

	void wrong_answer(const char *MSG)
	{
		printf("Wrong Answer: %s\n", MSG);
		exit(0);
	}

	void simulate()
	{
		if (S > S_MAX)
		{
			char str[50];
			sprintf(str, "over %d switches", S_MAX);
			wrong_answer(str);
		}
		for (int i = 0; i <= M; ++i)
		{
			if (!(-S <= IC[i] && IC[i] <= M))
			{
				wrong_answer("wrong serial number");
			}
		}
		for (int j = 1; j <= S; ++j)
		{
			if (!(-S <= IX[j - 1] && IX[j - 1] <= M))
			{
				wrong_answer("wrong serial number");
			}
			if (!(-S <= IY[j - 1] && IY[j - 1] <= M))
			{
				wrong_answer("wrong serial number");
			}
		}

		int P = 0;
		std::vector<bool> state(S + 1, false);
		int pos = IC[0];
		int k = 0;
		FILE *file_log = fopen("log.txt", "w");
		fprintf(file_log, "0\n");
		for (;;)
		{
			fprintf(file_log, "%d\n", pos);
			if (pos < 0)
			{
				if (++P > P_MAX)
				{
					fclose(file_log);
					char str[50];
					sprintf(str, "over %d inversions", P_MAX);
					wrong_answer(str);
				}
				state[-pos] = !state[-pos];
				pos = state[-pos] ? IX[-(1 + pos)] : IY[-(1 + pos)];
			}
			else
			{
				if (pos == 0)
				{
					break;
				}
				if (k >= N)
				{
					fclose(file_log);
					wrong_answer("wrong motion");
				}
				if (pos != A[k++])
				{
					fclose(file_log);
					wrong_answer("wrong motion");
				}
				pos = IC[pos];
			}
		}
		fclose(file_log);
		if (k != N)
		{
			wrong_answer("wrong motion");
		}
		for (int j = 1; j <= S; ++j)
		{
			if (state[j])
			{
				wrong_answer("state 'Y'");
			}
		}
		printf("Accepted: %d %d\n", S, P);
	}

} // namespace

void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y)
{
	if (answered)
	{
		wrong_answer("answered not exactly once");
	}
	answered = true;
	// check if input format is correct
	if ((int)C.size() != M + 1)
	{
		wrong_answer("wrong array length");
	}
	if (X.size() != Y.size())
	{
		wrong_answer("wrong array length");
	}
	S = X.size();
	IC = C;
	IX = X;
	IY = Y;
}

int main()
{
	M = read_int();
	N = read_int();
	A.resize(N);
	for (int k = 0; k < N; ++k)
	{
		A[k] = read_int();
	}

	answered = false;
	create_circuit(M, A);
	if (!answered)
	{
		wrong_answer("answered not exactly once");
	}
	FILE *file_out = fopen("out.txt", "w");
	fprintf(file_out, "%d\n", S);
	for (int i = 0; i <= M; ++i)
	{
		fprintf(file_out, "%d\n", IC[i]);
	}
	for (int j = 1; j <= S; ++j)
	{
		fprintf(file_out, "%d %d\n", IX[j - 1], IY[j - 1]);
	}
	fclose(file_out);
	simulate();
	return 0;
}

#endif

Compilation message

doll.cpp: In function 'int construct_recursive(int, int, int)':
doll.cpp:19:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   19 |  while (x.size() <= index)
      |         ~~~~~~~~~^~~~~~~~
doll.cpp:31:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   if (i >= a.size())
      |       ~~^~~~~~~~~~~
doll.cpp:40:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   if (i + (1 << level) >= a.size())
      |       ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for (int i = 0; i < A.size() - 1; i++) {
      |                  ~~^~~~~~~~~~~~~~
doll.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for (int i = 0; i < A.size(); i++) {
      |                  ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 23 ms 5124 KB Output is correct
3 Correct 23 ms 4716 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 10 ms 1372 KB Output is correct
6 Correct 31 ms 7112 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 23 ms 5124 KB Output is correct
3 Correct 23 ms 4716 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 10 ms 1372 KB Output is correct
6 Correct 31 ms 7112 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 59 ms 8916 KB Output is correct
9 Correct 71 ms 10952 KB Output is correct
10 Incorrect 67 ms 15344 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 23 ms 5124 KB Output is correct
3 Correct 23 ms 4716 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 10 ms 1372 KB Output is correct
6 Correct 31 ms 7112 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 59 ms 8916 KB Output is correct
9 Correct 71 ms 10952 KB Output is correct
10 Incorrect 67 ms 15344 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Partially correct 39 ms 9520 KB Output is partially correct
3 Partially correct 67 ms 8804 KB Output is partially correct
4 Partially correct 54 ms 9712 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Partially correct 39 ms 9520 KB Output is partially correct
3 Partially correct 67 ms 8804 KB Output is partially correct
4 Partially correct 54 ms 9712 KB Output is partially correct
5 Partially correct 99 ms 11600 KB Output is partially correct
6 Partially correct 58 ms 10820 KB Output is partially correct
7 Partially correct 89 ms 11208 KB Output is partially correct
8 Partially correct 46 ms 10492 KB Output is partially correct
9 Partially correct 39 ms 8692 KB Output is partially correct
10 Partially correct 51 ms 10240 KB Output is partially correct
11 Partially correct 45 ms 9716 KB Output is partially correct
12 Partially correct 39 ms 8696 KB Output is partially correct
13 Partially correct 44 ms 10192 KB Output is partially correct
14 Partially correct 44 ms 9540 KB Output is partially correct
15 Partially correct 78 ms 10036 KB Output is partially correct
16 Partially correct 2 ms 604 KB Output is partially correct
17 Correct 24 ms 5948 KB Output is correct
18 Partially correct 42 ms 9424 KB Output is partially correct
19 Partially correct 56 ms 8696 KB Output is partially correct
20 Partially correct 46 ms 9972 KB Output is partially correct
21 Partially correct 48 ms 9708 KB Output is partially correct
22 Partially correct 76 ms 9712 KB Output is partially correct