Submission #1154734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154734		nguyn	Xylophone (JOI18_xylophone)	C++20	0 / 100	0 ms	416 KiB

xylophone

#include <bits/stdc++.h>

#include "xylophone.h"
using namespace std;

#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>
	
int vis[5005];
int a[5005];
int nn; 

bool valid(int x) {
	return (x >= 1 && x <= nn && !vis[x]); 
}

void solve(int n) {
	nn = n;
	int l = 1;
	int r = n; 
	int id = 0; 
	while(l <= r) {
		int mid = (l + r) / 2; 
		if (query(1, mid) == n - 1) {
			r = mid - 1; 
			id = mid; 
		}
		else {
			l = mid + 1; 
		}
	}
	a[id] = n; 
	a[id + 1] = n - query(id, id + 1);
	a[id - 1] = n - query(id - 1, id); 
	vis[n] = 1;
	vis[a[id + 1]] = 1;
	vis[a[id - 1]] = 1; 
	for (int i = id + 2; i <= n; i++) {
		int t = query(i - 1, i); 
		int t1 = a[i - 1] - t;
		int t2 = a[i - 1] + t; 
		if (valid(t1) && valid(t2)) {
			t = query(i - 2, i); 
			if (valid(a[i - 2] + t)) {
				if (a[i - 2] + t == t1 || a[i - 2] + t == t2) {
					a[i] = a[i - 2] + t; 
					vis[a[i - 2] + t] = 1; 
				} 
			}
			else if (valid(a[i - 2] - t)) {
				if (a[i - 2] - t == t1 || a[i - 2] - t == t2) {
					a[i] = a[i - 2] - t; 
					vis[a[i - 2] - t] = 1;
				}
			}
		}
		else if (valid(t1)) {
			vis[t1] = 1;
			a[i] = t1; 
		} 
		else {
			vis[t2] = 1; 
			a[i] = t2;
		}
	}
	for (int i = id - 2; i >= 1; i--) {
		int t = query(i, i + 1); 
		int t1 = a[i + 1] - t;
		int t2 = a[i + 1] + t; 
		if (valid(t1) && valid(t2)) {
			t = query(i + 2, i); 
			if (valid(a[i + 2] + t)) {
				if (a[i + 2] + t == t1 || a[i + 2] + t == t2) {
					a[i] = a[i + 2] + t; 
					vis[a[i + 2] + t] = 1; 
				} 
			}
			else if (valid(a[i + 2] - t)) {
				if (a[i + 2] - t == t1 || a[i + 2] - t == t2) {
					a[i] = a[i + 2] - t; 
					vis[a[i + 2] - t] = 1;
				}
			}
		}
		else if (valid(t1)) {
			vis[t1] = 1;
			a[i] = t1; 
		} 
		else {
			vis[t2] = 1; 
			a[i] = t2;
		}
	}
	
	for (int i = 1; i <= n; i++) {
		answer(i, a[i]); 
	}
}

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