Submission #381070

#	Time	Username	Problem	Language	Result	Execution time	Memory
381070		aryan12	Xylophone (JOI18_xylophone)	C++17	100 / 100	141 ms	620 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;

static int A[5000];

void solve(int n) {
	int diff[n + 1];
	int signs[n + 1];
	for(int i = 0; i <= n; i++) {
		signs[i] = 0;
	}
	for(int i = 1; i < n; i++) {
		diff[i] = query(i, i + 1);
	}
	signs[1] = diff[1];
	for(int i = 1; i < n - 1; i++) {
		int x = query(i, i + 2);
		if(x == diff[i] + diff[i + 1]) {
			signs[i + 1] = (signs[i] < 0) ? -diff[i + 1] : diff[i + 1];
		}
		else {
			signs[i + 1] = (signs[i] < 1) ? diff[i + 1] : -diff[i + 1];
		}
	}
	int minTillNow = 0, maxTillNow = 0;
	int cur = 0, pos = 0;
	for(int i = 1; i < n; i++) {
		cur += signs[i];
		minTillNow = min(minTillNow, cur);
		maxTillNow = max(maxTillNow, cur);
		if(maxTillNow - minTillNow == n - 1) {
			pos = i + 1;
			if(signs[i] < 0) {
				for(int j = 1; j < n; j++) {
					signs[j] = -signs[j];
				}
			}
			break;
		}
	}
	int ans[n + 1];
	ans[pos] = n;
	for(int i = pos; i < n; i++) {
		ans[i + 1] = ans[i] + signs[i];
	}
	for(int i = pos - 1; i > 0; i--) {
		ans[i] = ans[i + 1] + -signs[i];
	}
	for(int i = 1; i <= n; i++) {
		answer(i, ans[i]);
	}
}

Compilation message (stderr)

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

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