Submission #1156720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156720		zhasyn	Xylophone (JOI18_xylophone)	C++20	100 / 100	18 ms	444 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 3 *1e5 + 100, M = 4096 + 10, len = 21, inf = 1e18;
const ll mod = 1e9 + 7;
ll um(ll a, ll b){
	return (1LL * a * b) % mod;
}
ll subr(ll a, ll b){
	return ((1LL * a - b) % mod + mod) % mod;
}

static int A[5000];
int cur[N], dif[N];
bool was[N];
void solve(int n) {
	int l = 1, r = n, rx;
	while(r - l > 1){
		int mid = (r + l) / 2;
		if(query(1, mid) == n - 1) r = mid;
		else l = mid;
	}
	rx = r;
	cur[rx] = n;
	was[n] = true;
	for(int i = rx + 1; i <= n; i++){
		int rs = query(i - 1, i);
		int fr = cur[i - 1] - rs, sc = cur[i - 1] + rs;
		if(sc > n || was[sc]){
			cur[i] = fr;
			was[fr] = true;
			continue;
		}
		if(fr < 1 || was[fr]){
			cur[i] = sc;
			was[sc] = true;
			continue;
		}
		int rs2 = query(i - 2, i);
		if(rs2 == abs(cur[i - 1] - cur[i - 2])){
			if(cur[i - 2] > cur[i - 1]) cur[i] = sc;
			else cur[i] = fr;
		} else{
			if(rs2 == rs){
				if(cur[i - 2] > cur[i - 1]) cur[i] = sc;
				else cur[i] = fr;
			} else{
				if(cur[i - 2] > cur[i - 1]) cur[i] = fr;
			else cur[i] = sc;
			}
		}
		was[cur[i]] = true;
	}
	
	for(int i = rx - 1; i >= 1; i--){
		int rs = query(i, i + 1);
		int fr = cur[i + 1] - rs, sc = cur[i + 1] + rs;
		if(sc > n || was[sc]){
			cur[i] = fr;
			was[fr] = true;
			continue;
		}
		if(fr < 1 || was[fr]){
			cur[i] = sc;
			was[sc] = true;
			continue;
		}
		int rs2 = query(i, i + 2);
		if(rs2 == abs(cur[i + 1] - cur[i + 2])){
			if(cur[i + 2] > cur[i + 1]) cur[i] = sc;
			else cur[i] = fr;
		} else{
			if(rs2 == rs){
				if(cur[i + 2] > cur[i + 1]) cur[i] = sc;
				else cur[i] = fr;
			} else{
				if(cur[i + 2] > cur[i + 1]) cur[i] = fr;
			else cur[i] = sc;
			}
		}
		was[cur[i]] = true;
	}
	
	for(int i = 1; i <= n; i++) {
		answer(i, cur[i]);
	}

}

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