Submission #1323118

#TimeUsernameProblemLanguageResultExecution timeMemory
1323118dadadadadMP3 Player (CEOI10_mp3player)C++20
10 / 100
27 ms1724 KiB

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define str string
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
 
const ll N = 1e5+5, INF = INT_MAX, MOD = 1e9 + 7;
const ll INFL = LLONG_MAX;

int ava (vector <pii> &p, int n, int vm, int v, int t) {
	deque <int> d;
	for(int i = 0; i < v; i ++) d.push_front(0);
	d.push_front(1);
	for(int i = v + 1; i <= vm; i ++) d.push_front(0);
	
	for(int i = 0; i < n - 1; i ++) {
		if(p[i].se - p[i + 1].se > t) continue;
		if(p[i].fi == 1) {
			if(d.front() == 1) {
				d.pop_back();
				d.push_front(1);
			}
			else{
				d.pop_back();
				d.push_front(0);
			}
		}
		else{
			if(d.back() == 1) {
				d.pop_front();
				d.push_back(1);
			}
			else{
				d.pop_front();
				d.push_back(0);
			}
		}
	}
	while(!d.empty() && d.front() == 0) d.pop_front();
//		cout << t << ' ' << d.size() - 1 << '\n';
	if(d.empty()) return -1;
	return d.size() - 1;
}

void solve(){
	int n, vm, v;
	cin >> n >> vm >> v;
	
	vector <pii> p(n);
	for(int i = 0; i < n; i ++) {
		char c;
		int m;
		cin >> c >> m;
		if(c == '+') p[i] = {1, m};
		else p[i] = {-1, m};
	}
	
	vector <int> T;
	T.pb(0);
	for(int i = 1; i < n; i ++) {
		T.pb(p[i].se - p[i - 1].se - 1);
	}
	T.pb(INF);
	
	sort(all(T));
	
	reverse(all(p));
	
	int l = 0, r = T.size() - 1, mx = -1, v2;
	while(l <= r) {
		int m = (l + r) / 2;
		int gt = ava(p, n, vm, v, T[m]);
		if(gt != -1) {
			mx = T[m];
			v2 = gt;
			l = m + 1;
		}
		else{
			r = m - 1;
		}
	}
	if(mx == INF) cout << "infinity";
	else cout << mx << ' ' << v2;
}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
//	freopen(s".in", "r", stdin); 
//	freopen(s".out", "w", stdout);
	
	
	int t;
	t = 1;
	
	
//	cin >> t;
	for(int i = 1; i <= t; i ++) {
//		cout << "Case " << i << ":\n";
		solve();
//		clean();
	}
	
// 	while(cin >> n){
// 	    solve();
// 	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...