oj.uz

Submission #131466

# Submission time Handle Problem Language Result Execution time Memory
131466 2019-07-17T07:32:37 Z 이온조(#3179) Sparklers (JOI17_sparklers) C++14
0 / 100
 2 ms 376 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
long long X[100009], mx;
int N, K, T, s;

void show() {
	printf("K: %d\n", K);
	for(int i=1; i<=N; i++) printf("%lld ", X[i]);
	puts("");
}

bool solve() {
	// show();
	long long l = X[K], r = X[K], ti = 0;
	for(int i=K-1; i>=1; i--) {
		ti += T;
		l -= T*s;
		r = min(r + T*s, X[i] + 1LL*ti*s);
		if(l > r) return false;
	}
	for(int i=K+1; i<=N; i++) {
		ti += T;
		r += T*s;
		if(r < X[i] - 1LL*ti*s) return false;
	}
	return true;
}

void rev() {
	K = N - K + 1;
	for(int i=0; i<=N+1; i++) X[i] = mx - X[i];
	reverse(X, X+N+2);
}

int main() {
	scanf("%d%d%d",&N,&K,&T);
	for(int i=1; i<=N; i++) scanf("%lld",&X[i]);
	X[0] = X[1]; X[N+1] = X[N];
	mx = X[N];

	int l = 1, r = INF;
	while(l <= r) {
		s = l+r >> 1;
		bool f1 = solve(); rev(); //printf("result: %d\n\n", f1);
		bool f2 = solve(); rev(); //printf("result: %d\n\n", f2);
		if(f1 || f2) r = s-1;
		else l = s+1;
	}
	printf("%d", r+1);
	return 0;
}

Compilation message

sparklers.cpp: In function 'int main()':
sparklers.cpp:45:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   s = l+r >> 1;
       ~^~
sparklers.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&N,&K,&T);
  ~~~~~^~~~~~~~~~~~~~~~~~~
sparklers.cpp:39:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=N; i++) scanf("%lld",&X[i]);
                          ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 30.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 50.0

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