Submission #1256923

#TimeUsernameProblemLanguageResultExecution timeMemory
1256923ro9669Festival (IOI25_festival)C++20
51 / 100
69 ms9908 KiB
#include "festival.h" #include <bits/stdc++.h> #define sz(a) int(a.size()) #define all(a) a.begin(),a.end() #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int , int> ii; const ll inf = ll(1e18); const int maxN = int(2e5)+7; int w; vector<int> p , t; ll cost(ll cur , int i){ ll tmp = cur - 1ll * p[i]; if (tmp <= inf / t[i]) return 1ll * tmp * t[i]; else return inf; } namespace sub1{ bool check(){ int n = sz(p); for (int i = 0 ; i < n ; i++){ if (t[i] > 2) return false; } return true; } vector<ii> g[2]; ll S[maxN]; int calc(ll x){ int l = 0 , r = sz(g[0]) , ans = 0; while (l <= r){ int mid = (l + r) / 2; if (x >= S[mid]){ ans = mid; l = mid + 1; } else{ r = mid - 1; } } return ans; } vector<int> solve(){ int n = sz(p); for (int i = 0 ; i < n ; i++){ g[t[i] - 1].push_back({p[i] , i}); } sort(all(g[0])); sort(all(g[1])); S[0] = 0; for (int i = 0 ; i < sz(g[0]) ; i++){ S[i + 1] = S[i] + 1ll * g[0][i].fi; } pair<int , int> res = {calc(w) , 0}; ll cur = w; for (int i = 0 ; i < sz(g[1]) ; i++){ if (cur > g[1][i].fi){ cur = cost(cur , g[1][i].se); if (res.fi < i + 1 + calc(cur)){ res = {i + 1 + calc(cur) , i + 1}; } } } vector<int> ans; for (int i = 0 ; i < res.se ; i++) ans.push_back(g[1][i].se); for (int i = 0 ; i < res.fi - res.se ; i++) ans.push_back(g[0][i].se); return ans; } } namespace sub5{ vector<ii> g[4]; int id[4]; ll S[maxN]; int calc(ll x){ int l = 0 , r = sz(g[0]) , ans = 0; while (l <= r){ int mid = (l + r) / 2; if (x >= S[mid]){ ans = mid; l = mid + 1; } else{ r = mid - 1; } } return ans; } vector<int> solve(){ int n = sz(p); for (int i = 0 ; i < n ; i++){ g[t[i] - 1].push_back({p[i] , i}); } for (int i = 0 ; i < 4 ; i++){ sort(all(g[i])); id[i] = 0; } S[0] = 0; for (int i = 0 ; i < sz(g[0]) ; i++){ S[i + 1] = S[i] + 1ll * g[0][i].fi; } pair<int , int> res = {calc(w) , 0}; vector<int> tmp_lis; ll cur = w; while (true){ vector<int> tmp; for (int i = 1 ; i < 4 ; i++){ if (id[i] < sz(g[i])){ if (cur <= cost(cur , g[i][id[i]].se)) tmp.push_back(i); } } if (tmp.empty()) break; for (int i = 0 ; i < sz(tmp) ; i++){ for (int j = i + 1 ; j < sz(tmp) ; j++){ ll X = 1ll * (tmp[i] + 1) * tmp[j] * g[tmp[i]][id[tmp[i]]].fi; ll Y = 1ll * tmp[i] * (tmp[j] + 1) * g[tmp[j]][id[tmp[j]]].fi; if (Y <= X) swap(tmp[i] , tmp[j]); } } int pos = g[tmp[0]][id[tmp[0]]].se; cur = cost(cur , pos); tmp_lis.push_back(pos); id[tmp[0]]++; int X = calc(cur); if (X + sz(tmp_lis) > res.fi){ res = {X + sz(tmp_lis) , sz(tmp_lis)}; } } while (true){ vector<int> tmp; for (int i = 1 ; i < 4 ; i++){ if (id[i] < sz(g[i])){ if (cur >= g[i][id[i]].fi) tmp.push_back(i); } } if (tmp.empty()) break; for (int i = 0 ; i < sz(tmp) ; i++){ for (int j = i + 1 ; j < sz(tmp) ; j++){ ll X = 1ll * (tmp[i] + 1) * tmp[j] * g[tmp[i]][id[tmp[i]]].fi; ll Y = 1ll * tmp[i] * (tmp[j] + 1) * g[tmp[j]][id[tmp[j]]].fi; if (Y <= X) swap(tmp[i] , tmp[j]); } } int pos = g[tmp[0]][id[tmp[0]]].se; cur = cost(cur , pos); tmp_lis.push_back(pos); id[tmp[0]]++; int X = calc(cur); if (X + sz(tmp_lis) > res.fi){ res = {X + sz(tmp_lis) , sz(tmp_lis)}; } } vector<int> ans; for (int i = 0 ; i < res.se ; i++) ans.push_back(tmp_lis[i]); for (int i = 0 ; i < res.fi - res.se ; i++) ans.push_back(g[0][i].se); return ans; } } vector<int> max_coupons(int W , vector<int> P , vector<int> T){ w = W; p = P; t = T; //if (sub1::check()) return sub1::solve(); return sub5::solve(); } // int main(){ // ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("templete.inp" , "r" , stdin); // freopen("templete.out" , "w" , stdout); // int n , W; cin >> n >> W; // vector<int> P(n) , T(n); // for (int &x : P) cin >> x; // for (int &x : T) cin >> x; // vector<int> ans = max_coupons(W , P , T); // cout << sz(ans) << "\n"; // //for (int x : ans) cout << x << " "; // //cerr << sz(ans) << " " << n << "\n"; // 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...