oj.uz

Submission #131504

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

const int INF = 1e9;
const long long linf = 1LL * 1e18;
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("");
}

int rm[100009];

void go(int l, int r) {
	if(r <= rm[l] || X[l] + 1LL*(r-l)*T*s < X[r] - 1LL*(r-l)*T*s) return;
	rm[l] = r;
	if(r < N) go(l, r+1);
	if(1 < l) go(l-1, r);
}

bool solve() {
	// show();
	for(int i=1; i<=N; i++) rm[i] = 0;
	go(K, K);
	return (rm[1] == N);
}

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]);
	if(X[1] == X[N]) return !printf("0");
	mx = X[N];

	int l = 1, r = INF;
	while(l <= r) {
		s = l+r >> 1;
		bool f1 = solve(); rev(); //printf("speed: %d, result: %d\n\n", s, f1);
		bool f2 = solve(); rev(); //printf("speed: %d, result: %d\n\n", s, 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 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Incorrect 2 ms 376 KB Output isn't correct
13 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 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Incorrect 2 ms 376 KB Output isn't correct
13 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 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Incorrect 2 ms 376 KB Output isn't correct
13 Halted 0 ms 0 KB -