Submission #1156737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156737		Zflop	Xylophone (JOI18_xylophone)	C++20	100 / 100	34 ms	20752 KiB

xylophone

#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
int v[10000][2],q[5001][5001],cnt[5001];
void solve(int N) {
	v[1][0] = 1;
	q[1][2] = query(1,2);
	v[2][0] = 1 + q[1][2];
	v[1][1] = N;
	v[2][1] = N - q[1][2];
	for (int i = 3; i <= N;++i) {
		q[i - 2][i] = query(i - 2,i);
		q[i - 1][i] = query(i - 1,i);
		}
	for (int b = 0; b < 2;++b)
		for (int i = 3; i <= N;++i) {
			int a = q[i - 2][i];
			int d = abs(v[i - 1][b] - v[i - 2][b]);
			if (d == a) {
				int dif = q[i - 1][i];
				if (v[i - 1][b] > v[i - 2][b]) {
					v[i][b] = v[i - 1][b] - dif;
					}
				else
					v[i][b] = v[i - 1][b] + dif;
				}
			else {
				int r = abs(v[i - 1][b] - v[i - 2][b]);
				int dif = q[i - 1][i];
				if (dif + r == a) {
					if (v[i - 1][b] > v[i - 2][b])
						v[i][b] = v[i - 1][b] + dif;
					else
						v[i][b] = v[i - 1][b] - dif;
					}
				else {
					if (v[i - 2][b] > v[i - 1][b])
						v[i][b] = v[i - 1][b] + dif;
					else
						v[i][b] = v[i - 1][b] - dif;
					}
				}
			}
	for (int b = 0; b < 2;++b) {
		int mn = v[1][b];
		for (int i = 1; i <= N;++i)
			mn = min(mn,v[i][b]);
		for (int i = 1; i <= N;++i) {
			v[i][b] -= (mn - 1);
			//cout << v[i][b] << ' ';
			cnt[v[i][b]]++;
			if (v[i][b] == N) {
				if (cnt[1] == 0) {
					cnt[N] = 0;
					}
				}
			}
		bool ok = true;
		for (int i = 1; i <= N;++i) {
			if (cnt[i] == 0) {
				ok = false;
				}
			cnt[i] = 0;
			}
		if (ok) {
			for (int i = 1; i <= N;++i) 
				answer(i,v[i][b]);
			return;
			}
		}
	}

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