Submission #1154790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154790		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)) {
			int tt = query(i - 2, i);
			if (tt == abs(a[i - 2] - a[i - 1])) {
				if (a[i - 2] < a[i - 1]) {
					a[i] = t1;
					vis[a[i]] = 1; 
				}
				else {
					a[i] = t2;
					vis[a[i]] = 1; 
				}
			}
			else if (t == tt) {
				if (a[i - 1] > a[i - 2]) a[i] = t1;
				else a[i] = t2;
				vis[a[i]] = 1; 
			}
			else {
				if (a[i - 1] < a[i - 2]) a[i] = a[i - 2] - tt;
				else a[i] = a[i - 2] + tt;
				vis[a[i]] = 1;  
			}
		}
		else if (valid(t1)) {
			a[i] = t1; 
			vis[a[i]] = 1; 
		} 
		else { 
			a[i] = t2;
			vis[a[i]] = 1; 
		}
		vis[a[i]] = 1; 
	}
	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)) {
			int tt = query(i, i + 2);
			if (tt == abs(a[i + 2] - a[i + 1])) {
				if (a[i + 2] - a[i + 1] > 0) {
					a[i] = t2;
					vis[a[i]] = 1; 
				}
				else {
					a[i] = t1;
					vis[a[i]] = 1; 
				}
			} 
			else if (tt == t) {
				if (a[i + 1] < a[i + 2]) {
					a[i] = t2;
					vis[a[i]] = 1; 
				}
				else {
					a[i] = t1; 
					vis[a[i]] = 1; 
				}
			}
			else {
				if (a[i + 1] < a[i + 2]) {
					a[i] = a[i + 2] - tt;
					vis[a[i]] = 1; 
				}
				else {
					a[i] = a[i + 2] + tt;
					vis[a[i]] = 1; 
				}
			}
		}
		else if (valid(t1)) {
			a[i] = t1; 
			vis[a[i]] = 1; 
		} 
		else {
			a[i] = t2;
			vis[a[i]] = 1; 
		}
		
	}
	
	for (int i = 1; i <= n; i++) {
//		assert(a[i] > 0 && a[i] <= n);
//		cout << a[i] << ' '; 
		answer(i, a[i]); 
	}
}

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