oj.uz

답안 #1074137

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1074137 2024-08-25T08:17:46 Z Elias 자동 인형 (IOI18_doll) C++17
39 / 100
 61 ms 15356 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)
{
	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(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 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:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for (int i = 0; i < A.size() - 1; i++) {
      |                  ~~^~~~~~~~~~~~~~
doll.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for (int i = 0; i < A.size(); i++) {
      |                  ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 18 ms 4972 KB Output is correct
3 Correct 15 ms 4460 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 27 ms 7120 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 18 ms 4972 KB Output is correct
3 Correct 15 ms 4460 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 27 ms 7120 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 35 ms 8972 KB Output is correct
9 Correct 48 ms 10960 KB Output is correct
10 Incorrect 61 ms 15356 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 18 ms 4972 KB Output is correct
3 Correct 15 ms 4460 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 27 ms 7120 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 35 ms 8972 KB Output is correct
9 Correct 48 ms 10960 KB Output is correct
10 Incorrect 61 ms 15356 KB Output isn't correct
11 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 37 ms 9420 KB Output is partially correct
3 Partially correct 36 ms 8700 KB Output is partially correct
4 Partially correct 47 ms 9720 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 37 ms 9420 KB Output is partially correct
3 Partially correct 36 ms 8700 KB Output is partially correct
4 Partially correct 47 ms 9720 KB Output is partially correct
5 Partially correct 52 ms 11600 KB Output is partially correct
6 Partially correct 51 ms 10960 KB Output is partially correct
7 Partially correct 52 ms 11192 KB Output is partially correct
8 Partially correct 47 ms 10496 KB Output is partially correct
9 Partially correct 37 ms 8696 KB Output is partially correct
10 Partially correct 48 ms 10240 KB Output is partially correct
11 Partially correct 43 ms 9712 KB Output is partially correct
12 Partially correct 38 ms 8696 KB Output is partially correct
13 Partially correct 42 ms 10196 KB Output is partially correct
14 Partially correct 60 ms 9536 KB Output is partially correct
15 Partially correct 45 ms 9940 KB Output is partially correct
16 Partially correct 2 ms 600 KB Output is partially correct
17 Correct 24 ms 5844 KB Output is correct
18 Partially correct 42 ms 9420 KB Output is partially correct
19 Partially correct 42 ms 8696 KB Output is partially correct
20 Partially correct 45 ms 9976 KB Output is partially correct
21 Partially correct 49 ms 9712 KB Output is partially correct
22 Partially correct 42 ms 9720 KB Output is partially correct