Submission #1261585

#TimeUsernameProblemLanguageResultExecution timeMemory
1261585garam1732Festival (IOI25_festival)C++20
Compilation error
0 ms0 KiB
//#include "festival.h" #include <bits/stdc++.h> using namespace std; #define ff first #define ss second #define bl ' ' #define endl '\n' #define all(v) (v).begin(), (v).end() #define comp(v) (v).erase(unique(all(v)), (v).end()) #define lbd(v,x) lower_bound(all(v), (x))-(v).begin() #define ubd(v,x) upper_bound(all(v), (x))-(v).begin() typedef long long ll; typedef pair<int, int> pi; typedef pair<pi, int> pii; typedef pair<int, pi> ipi; typedef pair<pi, pi> pipi; typedef pair<ll, ll> pll; const int MAXN = 100100*2; const ll MOD = 1e9+7; const ll INF = 1e15; struct Coupon { ll p, t, n; bool operator < (const Coupon& x) const { if((t==1)^(x.t==1)) return x.t==1; if(t==1) return p<x.p; return p*t*(x.t-1) < x.p*x.t*(t-1); } } arr[MAXN]; vector<int> lst[5]; const int MAXM = 20; ll dp[MAXM][MAXM][MAXM][MAXM]; vector<int> pv[MAXM][MAXM][MAXM][MAXM]; vector<int> res, res1; std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) { int n = P.size(); for(int i=0; i<n; i++) arr[i] = {P[i],T[i], i}; sort(arr, arr+n);//for(int i=0;i<n;i++)cout<<arr[i].n<<bl;cout<<endl; int idx=0; ll cur=A; while(idx<n && cur<INF) { if((cur-arr[idx].p)*arr[idx].t < cur) break; res.push_back(arr[idx].n); cur = arr[idx].t*(cur-arr[idx].p); idx++; } if(cur>=INF) { while(idx<n) res.push_back(arr[idx++].n); return res; } for(int t=1;t<=4;t++) lst[t] = {-1}; for(int i=idx;i<n;i++) { lst[arr[i].t].push_back(i); } pair<int, vector<int> > mx = make_pair(0, vector<int>{0}); for(int i=0;i<MAXM&&i<lst[1].size();i++) { for(int j=0;j<MAXM&&j<lst[2].size();j++) { for(int k=0;k<MAXM&&k<lst[3].size();k++) { for(int l=0;l<MAXM&&l<lst[4].size();l++) { if(!i && !j && !k && !l) { dp[i][j][k][l] = cur; } else { int x = max(max(lst[1][i], lst[2][j]), max(lst[3][k], lst[4][l])); int di = (lst[1][i]==x); int dj = (lst[2][j]==x); int dk = (lst[3][k]==x); int dl = (lst[4][l]==x); if(dp[i-di][j-dj][k-dk][l-dl] >= arr[x].p) { ll tmp = arr[x].t*(dp[i-di][j-dj][k-dk][l-dl]-arr[x].p); if(dp[i][j][k][l] <= tmp) { dp[i][j][k][l] = tmp; pv[i][j][k][l] = {i-di, j-dj, k-dk, l-dl}; } mx = max(mx, make_pair(i+j+k+l, vector<int>{i,j,k,l})); } } } } } } if(mx.ff == 0) return res; vector<int> v = mx.ss; while(v[0]+v[1]+v[2]+v[3]) {//for(int x:v)cout<<x<<bl;cout<<endl;cout.flush(); int x=0; for(int t=1;t<=4;t++) x=max(x, lst[t][v[t-1]]); res1.push_back(arr[x].n); v = pv[v[0]][v[1]][v[2]][v[3]]; } reverse(all(res1)); for(int x:res1) res.push_back(x); return res; } int main() { int N, A; assert(2 == scanf("%d %d", &N, &A)); std::vector<int> P(N), T(N); for (int i = 0; i < N; i++) assert(2 == scanf("%d %d", &P[i], &T[i])); fclose(stdin); std::vector<int> R = max_coupons(A, P, T); int S = R.size(); printf("%d\n", S); for (int i = 0; i < S; i++) printf("%s%d", (i == 0 ? "" : " "), R[i]); printf("\n"); fclose(stdout); return 0; }

Compilation message (stderr)

/usr/bin/ld: /tmp/ccQuB5T1.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccX5rs2f.o:festival.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status