oj.uz

답안 #1074176

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1074176 2024-08-25T08:35:41 Z Elias 자동 인형 (IOI18_doll) C++17
37 / 100
 405 ms 39412 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 wrong(const char *MSG)
{
	printf("Wrong Answer: %s\n", MSG);
	assert(false);
	exit(0);
}

void sim(vector<int> A, vector<int> c, vector<int> x, vector<int> y, int N, int M)
{
	int S = x.size();
	auto IC = c;
	auto IX = x;
	auto IY = y;
	constexpr int p_MAX = 20000000;
	constexpr int s_MAX = 400000;

	if (S > s_MAX)
	{
		char str[50];
		sprintf(str, "over %d switches", s_MAX);
		wrong(str);
	}
	for (int i = 0; i <= M; ++i)
	{
		if (!(-S <= IC[i] && IC[i] <= M))
		{
			wrong("wrong serial number");
		}
	}
	for (int j = 1; j <= S; ++j)
	{
		if (!(-S <= IX[j - 1] && IX[j - 1] <= M))
		{
			wrong("wrong serial number");
		}
		if (!(-S <= IY[j - 1] && IY[j - 1] <= M))
		{
			wrong("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(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("wrong motion");
			}
			if (pos != A[k++])
			{
				fclose(file_log);
				wrong("wrong motion");
			}
			pos = IC[pos];
		}
	}
	fclose(file_log);
	if (k != N)
	{
		wrong("wrong motion");
	}
	for (int j = 1; j <= S; ++j)
	{
		if (state[j])
		{
			wrong("state 'Y'");
		}
	}
	//printf("Accepted: %d %d\n", S, P);
}

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());

	sim(A, c, x, y, A.size(), M);

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

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Partially correct 369 ms 36848 KB Output is partially correct
3 Partially correct 357 ms 36856 KB Output is partially correct
4 Partially correct 386 ms 37524 KB Output is partially correct

Subtask #6
28.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Partially correct 369 ms 36848 KB Output is partially correct
3 Partially correct 357 ms 36856 KB Output is partially correct
4 Partially correct 386 ms 37524 KB Output is partially correct
5 Partially correct 405 ms 39412 KB Output is partially correct
6 Partially correct 390 ms 39144 KB Output is partially correct
7 Partially correct 379 ms 39392 KB Output is partially correct
8 Partially correct 357 ms 38772 KB Output is partially correct
9 Partially correct 357 ms 36864 KB Output is partially correct
10 Partially correct 336 ms 38716 KB Output is partially correct
11 Partially correct 343 ms 38200 KB Output is partially correct
12 Partially correct 335 ms 37404 KB Output is partially correct
13 Partially correct 344 ms 37796 KB Output is partially correct
14 Partially correct 371 ms 38052 KB Output is partially correct
15 Partially correct 322 ms 38048 KB Output is partially correct
16 Partially correct 7 ms 1116 KB Output is partially correct
17 Correct 157 ms 18856 KB Output is correct
18 Partially correct 319 ms 37236 KB Output is partially correct
19 Partially correct 319 ms 37192 KB Output is partially correct
20 Partially correct 336 ms 38604 KB Output is partially correct
21 Partially correct 340 ms 38032 KB Output is partially correct
22 Partially correct 335 ms 38196 KB Output is partially correct