oj.uz

답안 #1074147

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1074147 2024-08-25T08:22:18 Z Elias 자동 인형 (IOI18_doll) C++17
37 / 100
 52 ms 11336 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>();
	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(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())
      |       ~~~~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 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 47 ms 9172 KB Output is partially correct
3 Partially correct 37 ms 9160 KB Output is partially correct
4 Partially correct 42 ms 10428 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 47 ms 9172 KB Output is partially correct
3 Partially correct 37 ms 9160 KB Output is partially correct
4 Partially correct 42 ms 10428 KB Output is partially correct
5 Partially correct 46 ms 11336 KB Output is partially correct
6 Partially correct 44 ms 11172 KB Output is partially correct
7 Partially correct 46 ms 11252 KB Output is partially correct
8 Partially correct 45 ms 10880 KB Output is partially correct
9 Partially correct 37 ms 9156 KB Output is partially correct
10 Partially correct 42 ms 10792 KB Output is partially correct
11 Partially correct 42 ms 10584 KB Output is partially correct
12 Partially correct 37 ms 9312 KB Output is partially correct
13 Partially correct 38 ms 9672 KB Output is partially correct
14 Partially correct 43 ms 9904 KB Output is partially correct
15 Partially correct 41 ms 9908 KB Output is partially correct
16 Partially correct 1 ms 604 KB Output is partially correct
17 Correct 26 ms 6016 KB Output is correct
18 Partially correct 43 ms 9556 KB Output is partially correct
19 Partially correct 42 ms 9348 KB Output is partially correct
20 Partially correct 44 ms 10684 KB Output is partially correct
21 Partially correct 52 ms 10592 KB Output is partially correct
22 Partially correct 44 ms 10624 KB Output is partially correct