oj.uz

Submission #563709

# Submission time Handle Problem Language Result Execution time Memory
563709 2022-05-18T03:34:09 Z ngpin04 Sure Bet (CEOI17_sure) C++14
100 / 100
 592 ms 3440 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
	return l + rd() % (r - l + 1);
}
const int N = 1e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
const int base = 1e4;

int need[2 * N];
int t[N];
int r[N];
int n;

int fix(string s) {
	int pos = 0;
	while (pos < (int) s.size() && s[pos] != '.')
		pos++;
	if (pos == (int) s.size())
		s += '.';
	int cnt = (int) s.size() - pos - 1;
	while (cnt < 4) {
		s += '0';
		cnt++;
	}
	
	// cerr << s << "\n";
	
	int res = 0;
	for (char c : s) 
		if (c != '.') 
			res = 10 * res + c - '0';
	return res;
}

bool solve(long long lim) {
	for (int i = 1; i <= 2 * n; i++)
		need[i] = 0;
			
	{
		long long tot = 0;
		for (int x = 1, i = 1; x <= 2 * n; x++) {
			while (i <= n && tot - x * base < lim) {
				tot += t[i];
				i++;
			}
			// cerr << tot << " " << x << " " << tot - x * base << " " << i << "\n";
			if (tot - x * base >= lim)
				need[x] += i - 1;
			else
				need[x] += oo;
		}
	}	
	
	{
		long long tot = 0;
		for (int x = 1, i = 1; x <= 2 * n; x++) {
			while (i <= n && tot - x * base < lim) {
				tot += r[i];
				i++;
			}
			if (tot - x * base >= lim)
				need[x] += i - 1;
			else
				need[x] += oo;
		}
	}
	
	for (int i = 1; i <= 2 * n; i++)
		if (need[i] <= i)
			return true;
	return false;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	freopen("sure.inp","r",stdin);
	freopen("sure.out","w",stdout);
	#endif
	cin >> n;
	for (int i = 1; i <= n; i++) {
		string x,y;
		cin >> x >> y;
		t[i] = fix(x);
		r[i] = fix(y);
		cerr << t[i] << " " << r[i] << "\n";
	}
	sort(t + 1, t + n + 1, greater <int>());
	sort(r + 1, r + n + 1, greater <int>());

	long long lo = 0;
	long long hi = 1e18;
	while (hi - lo > 1) {
		long long mid = (lo + hi) >> 1;
		if (solve(mid))
			lo = mid;
		else
			hi = mid;
	}
	
	
	cout << lo / base << ".";
	{
		int cnt = to_string(lo % base).size();
		while (cnt < 4) {
			cout << 0;
			cnt++;
		}
		cout << lo % base;
	}
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 6 ms 340 KB Output is correct
13 Correct 7 ms 340 KB Output is correct
14 Correct 6 ms 340 KB Output is correct
15 Correct 6 ms 344 KB Output is correct
16 Correct 6 ms 340 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 6 ms 340 KB Output is correct
13 Correct 7 ms 340 KB Output is correct
14 Correct 6 ms 340 KB Output is correct
15 Correct 6 ms 344 KB Output is correct
16 Correct 6 ms 340 KB Output is correct
17 Correct 549 ms 3068 KB Output is correct
18 Correct 552 ms 3028 KB Output is correct
19 Correct 551 ms 3076 KB Output is correct
20 Correct 554 ms 3156 KB Output is correct
21 Correct 554 ms 3360 KB Output is correct
22 Correct 538 ms 3076 KB Output is correct
23 Correct 547 ms 2996 KB Output is correct
24 Correct 557 ms 3188 KB Output is correct
25 Correct 539 ms 3052 KB Output is correct
26 Correct 592 ms 3440 KB Output is correct