oj.uz

Submission #59877

# Submission time Handle Problem Language Result Execution time Memory
59877 2018-07-23T08:26:52 Z 김세빈(#1725) Sparklers (JOI17_sparklers) C++11
0 / 100
 3 ms 376 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll X[101010], L[101010], R[101010];
ll n, k, t;

bool check(ll v)
{	
	ll i, j, l, r, s, e, mid, p;
	
	L[1] = 2 * v * t;
	for(i=2; i<=n; i++){
		for(s=0, e=2*v*t; s<=e; ){
			mid = s + e >> 1;
			p = upper_bound(X+1, X+i, X[i] + mid - 2 * v * t) - X - 1;
			if(X[p] + L[p] >= X[i] + mid - 2 * v * t) s = mid + 1;
			else e = mid - 1;
		}
		L[i] = s - 1;
	}
	
	R[n] = 2 * v * t;
	for(i=n-1; i>=1; i--){
		for(s=0, e=2*v*t; s<=e; ){
			mid = s + e >> 1;
			p = upper_bound(X+i+1, X+n+1, X[i] - mid + 2 * v * t) - X;
			if(X[p] - R[p] <= X[i] - mid + 2 * v * t) s = mid + 1;
			else e = mid - 1;
		}
		R[i] = s - 1;
	}
	
//	printf("%lld\n", v);
	
//	for(i=1; i<=n; i++){
//		printf("%lld %lld\n", L[i], R[i]);
//	}
//	printf("\n");
	
	L[0] = 1e9; R[n+1] = 1e9;
	
	for(i=0; i<k; i++){
		for(j=k+1; j<=n+1; j++){
			if(L[i] < 0 || R[j] < 0) continue;
			if(i == k-1 && j == k+1) continue;
			
			l = min(X[i] + L[i], X[i+1]);
			r = max(X[j] - R[j], X[j-1]);
			s = max(X[k] - l, 0ll) + max(r - X[k], 0ll);
			if(s <= 2 * t * v) return 1;
		}
	}
	
	return 0;
}

int main()
{
	ll i, s, e, mid;
	
	scanf("%lld%lld%lld", &n, &k, &t);
	
	for(i=1; i<=n; i++){
		scanf("%lld", X+i);
	}
	
	for(s=0, e=1e9; s<=e; ){
		mid = s + e >> 1;
		if(check(mid)) e = mid - 1;
		else s = mid + 1;
	}
	
	printf("%lld\n", e + 1);
	
	return 0;
}

Compilation message

sparklers.cpp: In function 'bool check(ll)':
sparklers.cpp:17:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid = s + e >> 1;
          ~~^~~
sparklers.cpp:28:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid = s + e >> 1;
          ~~^~~
sparklers.cpp: In function 'int main()':
sparklers.cpp:71:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid = s + e >> 1;
         ~~^~~
sparklers.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &n, &k, &t);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", X+i);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -