oj.uz

Submission #428790

# Submission time Handle Problem Language Result Execution time Memory
428790 2021-06-15T14:31:59 Z oolimry Sparklers (JOI17_sparklers) C++17
0 / 100
 1 ms 204 KB 
#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 oL = L, oR = R;
			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){
				L = oL, R = oR;
				if(goright) e--;
				else s++; 
				goright = not goright;
				if(goright and e != n-1){
					//show(pos[e+1]);
					L = max(L, pos[e+1] - dis*T);
					R = min(R, pos[e+1] + dis*T);
					e++;
				}
				else if(not goright and s != 0){
					L = max(L, pos[s-1] - dis*T);
					R = min(R, pos[s-1] + dis*T);
					s--;
				}
				else can = false;
				
				if(L > R) can = false;
			}
			
			//show2(s,e);
			//show2(L,R);
		}
		
		if(can) high = mid;
		else low = mid;
	}
	
	cout << high;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -