Submission #566875

#	Time	Username	Problem	Language	Result	Execution time	Memory
566875		1zaid1	Xylophone (JOI18_xylophone)	C++17	100 / 100	105 ms	1092 KiB

xylophone

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

// static int A[5000];
const int M = 1e5+5;
int sm[M], ans[M];

map<pair<int, int>, int> mp;
int cry(int a, int b) {
	if (a == b) return 0;
	if (!mp[{a, b}]) mp[{a, b}] = query(a, b);
	return mp[{a, b}];
}

void solve(int n) {
	sm[1] = 0;
	for (int i = 1; i <= n-2; i++) {
		int a = cry(i, i+1);
		int b = cry(i+1, i+2);
		int c = cry(i, i+2);

		if (a + b == c) sm[i+1] = sm[i];
		else sm[i+1] = !sm[i];
	}

	ans[1] = 0;
	for (int i = 1; i < n; i++) {
		if (sm[i]) ans[i+1] = ans[i] - cry(i, i+1);
		else ans[i+1] = ans[i] + cry(i, i+1);
	}

	int mn = *min_element(ans+1, ans+n+1)-1;
	for (int i = 1; i <= n; i++) ans[i] -= mn;
	if (min_element(ans+1, ans+n+1)-ans > max_element(ans+1, ans+n+1)-ans) {
		for (int i = 1; i <= n; i++) ans[i] = n+1-ans[i];
	}

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

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