Submission #1156573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156573		zhasyn	Xylophone (JOI18_xylophone)	C++20	47 / 100	24 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];
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;
	
	for(int i = rx + 1; i <= n; i++){
		dif[i] = query(i - 1, i);
		int fr = cur[i - 1] - dif[i], sc = cur[i - 1] + dif[i];
		if(sc > n){
			cur[i] = fr;
			continue;
		}
		if(fr < 1){
			cur[i] = sc;
			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(cur[i - 2] > cur[i - 1]) cur[i] = fr;
			// else cur[i] = sc;
		// }
		int tmp = query(i - 2, i);

        if (tmp == dif[i] + dif[i - 1])
            cur[i] = cur[i - 2] - (cur[i - 2] - cur[i - 1]) / dif[i - 1] * tmp;
        else
            cur[i] = cur[i - 1] + (cur[i - 2] - cur[i - 1]) / dif[i - 1] * dif[i];
	}
	
	for(int i = rx - 1; i >= 1; i--){
		dif[i] = query(i, i + 1);
		int fr = cur[i + 1] - dif[i], sc = cur[i + 1] + dif[i];
		//cout << fr << " "<< sc << endl;
		if(sc > n){
			cur[i] = fr;
			continue;
		}
		if(fr < 1){
			cur[i] = sc;
			continue;
		}
		int tmp = query(i, i + 2);

        if (tmp == dif[i] + dif[i + 1])
        	cur[i] = cur[i + 2] - (cur[i + 2] - cur[i + 1]) / dif[i + 1] * tmp;
        else
            cur[i] = cur[i + 1] + (cur[i + 2] - cur[i + 1]) / dif[i + 1] * dif[i];
	}
	
	
	for(int i = 1; i <= n; i++) {
		answer(i, cur[i]);
	}

}

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