Submission #368345

#	Time	Username	Problem	Language	Result	Execution time	Memory
368345		idontreallyknow	Xylophone (JOI18_xylophone)	C++14	0 / 100	1 ms	364 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
static int A[5000];

void solve(int N) {
	if (N == 1) {
		answer(1,1);
		return;
	}
	vector<int> dif1(N+1), dif2(N+1);
	for (int q = 2; q <= N; q++) {
		dif1[q] = query(q-1,q);
		if (q > 2) dif2[q] = query(q-2,q);
	}
	vector<bool> sgn(N+1);
	for (int q = 3; q <= N; q++) {
		if (dif2[q] == dif1[q]+dif1[q-1]) sgn[q] = sgn[q-1];
		else sgn[q] = !sgn[q-1];
	}
	vector<int> pref(N+1);
	for (int q = 2; q <= N; q++) {
		if (sgn[q]) pref[q] = pref[q-1]+dif1[q];
		else pref[q] = pref[q-1]-dif1[q];
	}
	set<pair<int,int>> seen;
	bool rev = false;
	int lo = -1, hi = -1;
	for(int q = 1; q <= N; q++) {
		if (seen.size()) {
			int x = pref[q] - seen.begin()->first;
			if (abs(x) == N-1) {
				lo = seen.begin()->second;
				hi = q;
				if (x < 0) rev = true;
				break;
			}
			x = pref[q] - seen.rbegin()->first;
			if (abs(x) == N-1) {
				lo = seen.rbegin()->second;
				hi = q;
				if (x < 0) rev = true;
				break;
			}
		}
		seen.insert(make_pair(pref[q],q));
	}
	if (rev) {
		for (int q = 2; q <= N; q++) sgn[q] = !sgn[q];
	}
	vector<int> ans(N+1);
	ans[1] = 1-pref[lo];
	for (int q = 2; q <= N; q++) {
		if (sgn[q]) ans[q] = ans[q-1]+dif1[q];
		else ans[q] = ans[q-1]-dif1[q];
	}
	for (int q = 1; q <= N; q++) {
		answer(q,ans[q]);
	}
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:28:15: warning: variable 'hi' set but not used [-Wunused-but-set-variable]
   28 |  int lo = -1, hi = -1;
      |               ^~
xylophone.cpp: At global scope:
xylophone.cpp:4:12: warning: 'A' defined but not used [-Wunused-variable]
    4 | static int A[5000];
      |            ^

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