Submission #1253568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253568		thelegendary08	Festival (IOI25_festival)	C++17	100 / 100	387 ms	250912 KiB

festival

#include "festival.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<endl
#define dout(a) cout<<a<<' '<<#a<<endl
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<endl
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
const int lg = 75;
bool cmp(pair<pii,int> A, pair<pii,int> B){
	pii a = A.first; pii b = B.first;
	int x = 1e10;
	int c1 = ((x - a.first) * a.second - b.first) * b.second;
	int c2 = ((x - b.first) * b.second - a.first) * a.second;
	// pout(a); 
	// pout(b);
	// dout2(c1,c2);
	if(c1 != c2)return c2 < c1;
	else return a.first < b.first;
}
std::vector<signed> max_coupons(signed a, std::vector<signed> P, std::vector<signed> T) {
  	//P[i] * T[i] / (T[i] - 1)
  	
  	//(A - P[i]) * T[i] = A
  	//A - P[i] = A / T[i]
  	//A = A * T[i] - P[i] * T[i]
  	//A * (T[i] - 1) = P[i] * T[i]
  	//A = P[i] * T[i] / (T[i] - 1)
  	//current money larger than potential => increase
  	int A = a; 
  	
	vector<pair<pii,int>>w;
	int N = P.size();
	vpii os; 
	f0r(i, N){
		if(T[i] != 1)w.pb(mp(mp(P[i], T[i]), i));
		else os.pb(mp(P[i], i));
	}
	sort(all(os));
	vi ps;
	ps.pb(0);
	f0r(i, os.size()){
		ps.pb(ps.back() + os[i].first);
	}
	sort(w.begin(), w.end(), cmp);
	N = w.size();
	f0r(i, N){
		// dout2(w[i].first.first, w[i].first.second);
	}
	vector<signed>ans;
	/*
	vpii os; 
	f0r(i, N){
		if(T[i] != 1)w.pb(mp(mp(P[i], T[i]), i));
		else os.pb(mp(P[i], i));
	}
	sort(all(os));
	vi ps;
	ps.pb(0);
	f0r(i, os.size()){
		ps.pb(ps.back() + os[i].first);
	}
	sort(w.begin(), w.end(), cmp);
	N = w.size();
	f0r(i, N){
		// dout2(w[i].first.first, w[i].first.second);
	}
	vector<signed>ans;
	
	//subtask 6
	//dp[i][j] = last one taken is i, j taken in total, what is the max money?
	vector<vpii> dp(N, vpii(lg,mp(-1,-1)));
	dp[0][0] = mp(A,-1);
	if(A >= w[0].first.first){
		dp[0][1] = mp((A - w[0].first.first) * w[0].first.second, -1);
	}
	vpii tmp(lg, mp(-1,-1)); 
	f0r(i,lg)tmp[i] = dp[0][i];
	f0r(i,lg)tmp[i].second = 0;
	tmp[0].second = -1;
	FOR(i, 1, N){
		dp[i][0] = mp(A,-1);
		FOR(j, 1, lg){
			if(w[i].first.first <= tmp[j-1].first){
				dp[i][j] = mp((tmp[j-1].first - w[i].first.first) * w[i].first.second, tmp[j-1].second);
				if(dp[i][j].first > 1e17)dp[i][j].first = 1e17;
			}
		}
		f0r(j, lg){
			if(tmp[j].first < dp[i][j].first)tmp[j] = mp(dp[i][j].first, i);
		}
		// f0r(j,lg)cout<<tmp[j].first<<' '; cout<<endl;
	}
	
	f0r(i, N){
		// f0r(j,lg)cout<<dp[i][j].first<<' ';
		// cout<<'\n';
	}
	
	int mx = 0; pii mxd = mp(-1,-1); int ones = 0;
	f0r(i, N){
		f0r(j, lg){
			int lo = 0; int hi = ps.size() - 1; 
			while(lo < hi){
				int mid = lo + (hi - lo + 1) / 2;
				if(ps[mid] <= dp[i][j].first)lo = mid;
				else hi = mid - 1; 
			}
			int riyal = j + lo;
			if(dp[i][j].first != -1 && riyal > mx){
				mx = riyal; mxd = mp(i,j); ones = lo;
			}
		}
	}
	//dp[mxd][mx]
	
	int cur = mxd.first;
	int ptr = mxd.second;
	while(cur != -1){
		ans.pb(cur);
		// dout2(cur,ptr);
		cur = dp[cur][ptr].second;
		ptr--;
	}
	f0r(i, ans.size())ans[i] = w[ans[i]].second;
	reverse(all(ans));
	f0r(i, ones)ans.pb(os[i].second);
	*/
	//full sol
	if(N == 0){
		f0r(i, os.size()){
			if(A >= os[i].first){
				A -= os[i].first; ans.pb(os[i].second);
			}
		}
		return ans;
	}
	int fi = -1;
	f0r(i, w.size()){
		if((A - w[i].first.first) * w[i].first.second >= A){
			ans.pb(w[i].second);
			A = (A - w[i].first.first) * w[i].first.second;
			if(A > 1e17)A = 1e17;
		}
		else{
			fi = i; break;
		}
	}
	// cerr<<fi<<endl;
	if(fi != -1){
		
		
		vector<vpii> dp(N, vpii(lg,mp(-1,-1)));
		dp[fi][0] = mp(A,-1);
		if(A >= w[fi].first.first){
			dp[fi][1] = mp((A - w[fi].first.first) * w[fi].first.second, -1);
			if(dp[fi][1].first > 1e17)dp[fi][1].first = 1e17;
		}
		vpii tmp(lg, mp(-1,-1)); 
		f0r(i,lg)tmp[i] = dp[fi][i];
		f0r(i,lg)tmp[i].second = fi;
		tmp[0].second = -1;
		FOR(i, fi + 1, N){
			dp[i][0] = mp(A,-1);
			FOR(j, 1, lg){
				if(w[i].first.first <= tmp[j-1].first){
					dp[i][j] = mp((tmp[j-1].first - w[i].first.first) * w[i].first.second, tmp[j-1].second);
					if(dp[i][j].first > 1e17)dp[i][j].first = 1e17;
				}
			}
			f0r(j, lg){
				if(tmp[j].first < dp[i][j].first)tmp[j] = mp(dp[i][j].first, i);
			}
			// f0r(j,lg)cout<<tmp[j].first<<' '; cout<<endl;
		}
		
		f0r(i, N){
			// f0r(j,lg)cout<<dp[i][j].first<<' ';
			// cout<<'\n';
		}
		
		int mx = 0; pii mxd = mp(-1,-1); int ones = 0;
		FOR(i, fi, N){
			f0r(j, lg){
				int lo = 0; int hi = ps.size() - 1; 
				while(lo < hi){
					int mid = lo + (hi - lo + 1) / 2;
					if(ps[mid] <= dp[i][j].first)lo = mid;
					else hi = mid - 1; 
				}
				int riyal = j + lo;
				if(dp[i][j].first != -1 && riyal > mx){
					mx = riyal; mxd = mp(i,j); ones = lo;
				}
			}
		}
		// dout(N);
		//dp[mxd][mx]
		vi a2;
		int cur = mxd.first;
		int ptr = mxd.second;
		// cerr<<mx<<' '<<ones<<endl;
		while(cur != -1 && ptr != 0){
			a2.pb(cur);
			// dout2(cur,ptr);
			cur = dp[cur][ptr].second;
			ptr--;
		}
		f0r(i, a2.size())a2[i] = w[a2[i]].second;
		reverse(all(a2));
		f0r(i, ones)a2.pb(os[i].second);
		
		for(auto u : a2)ans.pb(u);
	}
	else{
		int lo = 0; int hi = ps.size() - 1; 
		while(lo < hi){
			int mid = lo + (hi - lo + 1) / 2;
			if(ps[mid] <= A)lo = mid;
			else hi = mid - 1; 
		}
		f0r(i, lo)ans.pb(os[i].second);
	}
	
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 27 / 27
• Subtask 6: 16 / 16
• Subtask 7: 18 / 18