oj.uz

Submission #1074152

# Submission time Handle Problem Language Result Execution time Memory
1074152 2024-08-25T08:25:46 Z Elias Mechanical Doll (IOI18_doll) C++17
37 / 100
 86 ms 11172 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;

// void sim(vector<int> c, vector<int> x, vector<int> y, int N, int M)
// {
// 	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);
// }

void wrong_answer(const char *MSG)
{
	printf("Wrong Answer: %s\n", MSG);
	exit(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>();
	max_levels = 0;

	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]);
	// 	}
	// }

	a = A;

	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(x.size() <= 2 * A.size());

	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 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:107:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |  while (x.size() <= index)
      |         ~~~~~~~~~^~~~~~~~
doll.cpp:119:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |   if (i >= a.size())
      |       ~~^~~~~~~~~~~
doll.cpp:128:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |   if (i + (1 << level) >= a.size())
      |       ~~~~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
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 #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 1 ms 348 KB Output is partially correct
2 Partially correct 37 ms 9124 KB Output is partially correct
3 Partially correct 41 ms 9224 KB Output is partially correct
4 Partially correct 59 ms 10516 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Output is partially correct
2 Partially correct 37 ms 9124 KB Output is partially correct
3 Partially correct 41 ms 9224 KB Output is partially correct
4 Partially correct 59 ms 10516 KB Output is partially correct
5 Partially correct 49 ms 11152 KB Output is partially correct
6 Partially correct 52 ms 11172 KB Output is partially correct
7 Partially correct 49 ms 11148 KB Output is partially correct
8 Partially correct 55 ms 10884 KB Output is partially correct
9 Partially correct 76 ms 9160 KB Output is partially correct
10 Partially correct 52 ms 10840 KB Output is partially correct
11 Partially correct 47 ms 10584 KB Output is partially correct
12 Partially correct 39 ms 9316 KB Output is partially correct
13 Partially correct 43 ms 9904 KB Output is partially correct
14 Partially correct 45 ms 9908 KB Output is partially correct
15 Partially correct 41 ms 9964 KB Output is partially correct
16 Partially correct 2 ms 604 KB Output is partially correct
17 Correct 25 ms 5976 KB Output is correct
18 Partially correct 41 ms 9392 KB Output is partially correct
19 Partially correct 83 ms 9420 KB Output is partially correct
20 Partially correct 84 ms 10836 KB Output is partially correct
21 Partially correct 86 ms 10528 KB Output is partially correct
22 Partially correct 57 ms 10580 KB Output is partially correct