답안 #113806

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
113806 2019-05-28T13:05:31 Z aminra Sparklers (JOI17_sparklers) C++14
0 / 100
3 ms 384 KB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)1e5 + 3;
const int infint = (int)1e9 + 3;
const ll inf = (ll)2e18;
int n, k, t;
int X[MAXN];
 
bool make(vector < ld > x, vector < ld > y)
{
	if (x[0] < y[0])
		return 0;
  	int ok = 1;
  	pair<int, int> L, R;
  	L = {0, 0};
  	R = {0, 0};
  	while (ok)
  	{
    	ok = 0;
    	while (L.first + 1 < x.size() && x[L.first + 1] >= y[R.second])
		{
      		ok = 1;
      		if (x[++L.first] > x[L.second])
			  	L.second = L.first;
    	}
		while (R.first + 1 < y.size() && y[R.first + 1] <= x[L.second])
		{
      		ok = 1;
      		if (y[++R.first] < y[R.second])
				R.second = R.first;
    	}
  	}
  	return L.first + 1 == x.size() && R.first + 1 == y.size();
}
 
bool check(int s)
{
	vector <ld> x, y;
	for (ll i = k; i >= 0; i--)
    	x.push_back(X[i] - (ld)2 * s * t * i);
  	for (ll i = k; i < n; i++)
    	y.push_back(X[i] - (ld)2 * s * t * i);
  	if (!make(x, y)) 
		return 0;
  	reverse(x.begin(), x.end());
  	reverse(y.begin(), y.end());
  	if (!make(x, y))
		return 0;
	return 1;
}
 
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> k >> t;
	k--;
	for (ll i = 0; i < n; i++)
    cin >> X[i];
  	int L = 0, R = infint;
  	while (R - L > 1)
  	{
		ll mid = (L + R) >> 1;
    	if (check(mid))
      		R = mid;
    	else
      		L = mid;
    }
	cout << R;
}

Compilation message

sparklers.cpp: In function 'bool make(std::vector<long double>, std::vector<long double>)':
sparklers.cpp:23:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      while (L.first + 1 < x.size() && x[L.first + 1] >= y[R.second])
             ~~~~~~~~~~~~^~~~~~~~~~
sparklers.cpp:29:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (R.first + 1 < y.size() && y[R.first + 1] <= x[L.second])
          ~~~~~~~~~~~~^~~~~~~~~~
sparklers.cpp:36:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    return L.first + 1 == x.size() && R.first + 1 == y.size();
           ~~~~~~~~~~~~^~~~~~~~~~~
sparklers.cpp:36:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    return L.first + 1 == x.size() && R.first + 1 == y.size();
                                      ~~~~~~~~~~~~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Incorrect 2 ms 384 KB Output isn't correct
20 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Incorrect 2 ms 384 KB Output isn't correct
20 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Incorrect 2 ms 384 KB Output isn't correct
20 Halted 0 ms 0 KB -