oj.uz

Submission #96687

# Submission time Handle Problem Language Result Execution time Memory
96687 2019-02-10T21:53:29 Z luciocf Xylophone (JOI18_xylophone) C++14
0 / 100
 2 ms 376 KB 
#include <bits/stdc++.h>
#include "xylophone.h"

using namespace std;

const int maxn = 5e3+10;

int n;
int num[maxn];
int dif[maxn][maxn];

bool maior[maxn];

void getQ(void)
{
	for (int i = 1; i < n; i++)
	{
		dif[i][i+1] = query(i, i+1);
		if (i < n-1) dif[i][i+2] = query(i, i+2);
	}
}

void solve(int N)
{
	n = N;

	getQ();

	maior[1] = 1;

	if (dif[1][3] == dif[1][2])
	{
		if (dif[1][2] > dif[2][3]) maior[2] = 0, maior[3] = 1; 
		else maior[2] = 1, maior[3] = 0;
	}
	else if (dif[1][3] < dif[1][2])
	{
		maior[3] = 0;
		if (dif[1][3] > dif[2][3]) maior[2] = 0;
		else maior[2] = 1;
	}
	else
	{
		maior[3] = 1;
		if (dif[1][3] < dif[2][3]) maior[2] = 1;
		else maior[2] = 0;
	}

	for (int i = 4; i <= n; i++)
	{
		if (dif[i-2][i] > dif[i-2][i-1]) maior[i] = 1;
		else if (dif[i-2][i] < dif[i-2][i-1]) maior[i] = 0;
		else if (maior[i-1]) maior[i] = 0;
		else maior[i] = 1;
	}

	int ind;

	for (int i = 1; i <= n; i++)
	{
		if (!maior[i]) continue;

		int x = dif[i-1][i];
		bool ok = 1;
		for (int j = i-1; j > 1; j--)
		{
			if (maior[j]) x += dif[j-1][j];
			else x -= dif[j-1][j];

			if (x < 0) ok = 0;
		}

		if (!ok) continue;

		if (maior[i+1]) continue;

		x = dif[i][i+1];
		ok = 1;
		for (int j = i+2; j <= n; j++)
		{
			if (maior[j]) x -= dif[j-1][j];
			else x += dif[j-1][j];

			if (x < 0) ok = 0;
		}

		if (ok)
		{
			ind = i;
			break;
		}
	}

	num[ind] = n;

	for (int i = ind-1; i >= 1; i--)
	{
		if (maior[i+1]) num[i] = num[i+1]-dif[i][i+1];
		else num[i] = num[i+1]+dif[i][i+1];
	}

	for (int i = ind+1; i <= n; i++)
	{
		if (maior[i]) num[i] = num[i-1]+dif[i-1][i];
		else num[i] = num[i-1]-dif[i-1][i];
	}

	for (int i = 1; i <= n; i++)
		answer(i, num[i]);
}

Compilation message

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:57:6: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int ind;
      ^~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 248 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 248 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 248 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -