Submission #752548

#	Time	Username	Problem	Language	Result	Execution time	Memory
752548		wenqi	Archery (IOI09_archery)	C++17	20 / 100	2091 ms	5964 KiB

archery

// trans rights
#include <bits/extc++.h>
using namespace std;
using ll = long long;

#ifdef DEBUG
#define D(args...) fprintf(stderr, args)
#else
#define D(...)
#endif

int N, R;
int rk[400005];
int me;

int G1[200005], G2[200005];

int f(int x, int y)
{
	if (x != y)
		return 0;
	return x;
}

int take_best(int x)
{
	if (x == 1)
		return 1;
	return -1;
}

int take_worst(int x)
{
	if (x == -1)
		return -1;
	return 1;
}

void trans(int *X)
{
	int x = X[0], y = X[N - 1];
	int w = f(take_worst(x), take_worst(y));
	for (int i = 0; i < N - 1; i++)
	{
		int p = i ? take_worst(X[i]) : take_best(X[i]);
		int q = take_best(X[i + 1]);
		X[i] = f(p, q);
	}
	X[N - 1] = w;
}

int main(int argc, const char *argv[])
{
	scanf(" %d %d", &N, &R);
	R = (R - 2 * N) % N + 2 * N;
	scanf(" %d", &me);
	for (int i = 0; i < 2 * N - 1; i++)
		scanf(" %d", &rk[i]);
	pair<int, int> ans = {N, 0};
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < i; j++)
		{
			int x = rk[2 * j], y = rk[2 * j + 1];
			if ((x < me) == (y < me))
				G1[j] = G2[j] = x < me ? -1 : 1;
			else
				G1[j] = G2[j] = 0;
		}
		int m = rk[2 * i];
		G1[i] = m < me ? -1 : 1;
		G2[i] = 0;
		for (int j = i + 1; j < N; j++)
		{
			int x = rk[2 * j - 1], y = rk[2 * j];
			if ((x < me) == (y < me))
				G1[j] = G2[j] = x < me ? -1 : 1;
			else
				G1[j] = G2[j] = 0;
		}
		for (int k = 0; k < R; k++)
		{
			trans(G1);
			trans(G2);
		}
		int e = 0;
		for (int j = 0; j < N; j++)
			if (G1[j] != G2[j])
				e = j;
		ans = min(ans, {e, -i});
	}
	printf("%d", -ans.second + 1);
	return 0;
}

Compilation message (stderr)

archery.cpp: In function 'int main(int, const char**)':
archery.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  scanf(" %d %d", &N, &R);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
archery.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf(" %d", &me);
      |  ~~~~~^~~~~~~~~~~~
archery.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   scanf(" %d", &rk[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 4 / 6
• Subtask 2: 16 / 94