Submission #428780

#	Time	Username	Problem	Language	Result	Execution time	Memory
428780		oolimry	Sparklers (JOI17_sparklers)	C++17	0 / 100	1 ms	320 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
#define l first
#define r second
typedef long long lint;
typedef pair<lint,lint> ii;

const lint inf = 1e17;
lint n, K, TT, T; 
lint pos[100005];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> K >> TT; K--;
	for(int i = 0;i < n;i++) cin >> pos[i];
	
	lint low = -1, high = 1e10 / TT;
	while(low != high-1){
		lint mid = (low+high)/2;
		T = mid * TT;
		
		bool can = true;
		int s = K, e = K;
		lint L = pos[K], R = pos[K];
		while(s != 0 or e != n-1){
			L -= T, R += T;
			
			bool goright = false;
			if(s == 0) goright = true;
			else if(e == n-1) goright = false;
			else if(L-pos[s-1] < pos[e+1]-R) goright = false;
			else goright = true;
			
			lint dis = e-s+1;
			if(goright){
				//show(pos[e+1]);
				L = max(L, pos[e+1] - dis*T);
				R = min(R, pos[e+1] + dis*T);
				e++;
			}
			else{
				//show(pos[s-1]);
				L = max(L, pos[s-1] - dis*T);
				R = min(R, pos[s-1] + dis*T);
				s--;
			}
			
			//show2(L,R);
			if(L > R) can = false;
		}
		
		if(can) high = mid;
		else low = mid;
	}
	
	cout << high;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50