Submission #763118

#	Time	Username	Problem	Language	Result	Execution time	Memory
763118		vjudge1	Xylophone (JOI18_xylophone)	C++17	100 / 100	87 ms	444 KiB

xylophone

#include <bits/stdc++.h>
#include "xylophone.h"

using namespace std;

const int NM = 5000;

int p[NM+5], q[NM+5];
bool used[NM+5];

void process(int p[NM+5], int i, int x, int y){
	if (p[i-2] < p[i-1]){
		if (p[i-1]-x < p[i-2]){
			if (y == x){
				p[i] = p[i-1]-x;
			}
			else{
				p[i] = p[i-1]+x;
			}
		}
		else{
			if (y == p[i-1]-p[i-2]){
				p[i] = p[i-1]-x;
			}
			else{
				p[i] = p[i-1]+x;
			}
		}
	}
	else{
		if (p[i-1]+x > p[i-2]){
			if (y == x){
				p[i] = p[i-1]+x;
			}
			else{
				p[i] = p[i-1]-x;
			}
		}
		else{
			if (y == p[i-2]-p[i-1]){
				p[i] = p[i-1]+x;
			}
			else{
				p[i] = p[i-1]-x;
			}
		}
	}
}

void modify(int N, int p[NM+5]){
	int mn = p[1];
	for (int i = 2; i <= N; i++)
		mn = min(mn, p[i]);
	for (int i = 1; i <= N; i++)
		p[i] += 1-mn;
}

bool ok(int N, int p[NM+5]){
	memset(used, 0, sizeof(used));
	int a, b;
	for (int i = 1; i <= N; i++){
		if (used[p[i]]) return 0;
		used[p[i]] = 1;
		if (p[i] == 1) a = i;
		if (p[i] == N) b = i;
	}
	return a < b;
}

void output(int N, int p[NM+5]){
	for (int i = 1; i <= N; i++)
		answer(i, p[i]);
}

void solve(int N){
	p[1] = 0;
	p[2] = query(1, 2);
	q[2] = -p[2];
	for (int i = 3; i <= N; i++){
		int x = query(i-1, i), y = query(i-2, i);
		process(p, i, x, y);
		process(q, i, x, y);
	}
	modify(N, p);
	modify(N, q);
	if (!ok(N, q)){
		output(N, p);
		return;
	}
	if (!ok(N, p)){
		output(N, q);
		return;
	}
	for (int i = 1; i <= N; i++){
		int mxp = p[i], mnp = p[i], mxq = q[i], mnq = q[i];
		for (int j = i+1; j <= N; j++){
			mxp = max(mxp, p[j]);
			mnp = min(mnp, p[j]);
			mxq = max(mxq, q[j]);
			mnq = min(mnq, q[j]);
			if ((mxp-mnp) != (mxq-mnq)){
				if (query(i, j) == mxq-mnq){
					output(N, q);
					return;
				}
				else{
					output(N, p);
					return;
				}
			}
		}
	}
}

Compilation message (stderr)

xylophone.cpp: In function 'bool ok(int, int*)':
xylophone.cpp:67:13: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |  return a < b;
      |             ^
xylophone.cpp:67:13: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]

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