Submission #1261586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261586		garam1732	Festival (IOI25_festival)	C++20	Compilation error	0 ms	0 KiB

festival

#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/ccKMk4md.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccHoZSzv.o:festival.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status