Submission #477584

#	Time	Username	Problem	Language	Result	Execution time	Memory
477584		izanbf	Xylophone (JOI18_xylophone)	C++14	100 / 100	126 ms	320 KiB

xylophone

#include "xylophone.h"
#include <vector>
using namespace std;

using vi = vector<int>;

static int A[5000];

void solution(int N, const vi& q2, const vi& q3, bool last_initial_assumption) {
	// last : el último era mayor que el de su izquierda?
	bool last = last_initial_assumption;
	vi s(N+1);
	
	if (last) 
		s[2] = s[1] + q2[1];
	else 
		s[2] = s[1] - q2[1];

	for (int i = 1; i <= N-2; ++i) {
		if (q3[i] != q2[i] + q2[i+1]) 
			last = not last;

		if (last) 
			s[i+2] = s[i+1] + q2[i+1];
		else
			s[i+2] = s[i+1] - q2[i+1];
	}

	int min_pos = 1;
	int max_pos = 1;
	for (int i = 2; i <= N; ++i) {
		if (s[i] < s[min_pos]) min_pos = i;
		if (s[i] > s[max_pos]) max_pos = i;
	}

	if (min_pos < max_pos) { // requisito solucion válida
		for (int i = 1; i <= N; ++i) {
			answer(i, s[i] - s[min_pos] + 1);
			// con s[i] - s[min_pos] + 1 desplazamos todos los valores
			// para que estén entre 1 y N
		} 
	}
}

void solve(int N) {
	vi q2(N+1), q3(N+1);
	for (int i = 1; i <= N-1; ++i) q2[i] = query(i, i+1);
	for (int i = 1; i <= N-2; ++i) q3[i] = query(i, i+2);
	solution(N, q2, q3, false);
	solution(N, q2, q3, true);
}

Compilation message (stderr)

xylophone.cpp:7:12: warning: 'A' defined but not used [-Wunused-variable]
    7 | static int A[5000];
      |            ^

• Subtask 1: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 53 / 53