Submission #1255632

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

festival

#include <bits/stdc++.h>

using namespace std;

#define int long long
const int N = 1e6 + 6;
typedef vector<int> vi;

struct Item 
{
    int p, t, idx;
} items[N];
int n, l_id, r_id;

bool cmp(Item a, Item b) 
{
    if (a.t == b.t && a.t == 1)
        return a.p < b.p;
    return a.p * a.t * (b.t - 1) < b.p * b.t * (a.t - 1);
}
vector<int> dp, res, chosen[N / 5];

void DFS(int pos, int cnt) 
{
    if (pos < l_id || cnt == 0) return;
    if (chosen[pos][cnt]) 
    {
        DFS(pos - 1, cnt - 1);
        res.push_back(items[pos].idx);
    } else {
        DFS(pos - 1, cnt);
    }
}

void Init(vector<int> &P, vector<int> &T) 
{
    n = (int)P.size();
    for (int i = 0; i < n; i++) {
        items[i] = {P[i], T[i], i};
    }
    sort(items, items + n, cmp);

    r_id = n;
    while (r_id > 0 && items[r_id - 1].t == 1)
        r_id--;
    l_id = r_id;
}

bool Greedy(int &A) 
{
    res.clear();
    for (int i = 0; i < r_id; i++) 
        if ((A - items[i].p) * items[i].t >= A) 
        {
            A = (A - items[i].p) * items[i].t;
            res.push_back(items[i].idx);
            if (A > 1e16) 
            {
                res.clear();
                for (int j = 0; j < n; j++)
                    res.push_back(items[j].idx);
                return true;
            }
        } else {
            l_id = i;
            break;
        }
    return false;
}

void DP(int A) 
{
    dp.clear();
    dp.push_back(A);
    for (int i = 0; i < n; i++) chosen[i].clear();
    for (int i = l_id; i < r_id; i++) 
    {
        int sz = (int)dp.size();
        chosen[i].resize(sz, 0);
        if ((dp[sz - 1] - items[i].p) * items[i].t >= 0) 
        {
            dp.push_back((dp[sz - 1] - items[i].p) * items[i].t);
            chosen[i].push_back(1);
        }
        for (int j = sz - 2; j >= 0; j--) 
        {
            if ((dp[j] - items[i].p) * items[i].t > dp[j + 1]) 
            {
                dp[j + 1] = (dp[j] - items[i].p) * items[i].t;
                chosen[i][j + 1] = 1;
            }
        }
    }
}

int FindBest() 
{
    int maxCount = 0, pos = 0;
    for (int i = 0; i < (int)dp.size(); i++) 
    {
        int cnt = 0;
        int low = r_id, high = n - 1;
        while (low < high) 
        {
            int mid = (low + high + 1) / 2;
            if (dp[i] >= items[mid].p) 
            {
                cnt = mid - r_id + 1;
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        if (i + cnt > maxCount) 
        {
            maxCount = i + cnt;
            pos = i;
        }
    }
    return pos;
}

vector<int> max_coupons(int A, vector<int> P, vector<int> T) 
{
    Init(P, T);
    if (Greedy(A)) return res;
    for (int i = r_id + 1; i < n; i++) {
        items[i].p += items[i - 1].p;
    }
    DP(A);
    int pos = FindBest();
    DFS(r_id - 1, pos);
    int remain = dp[pos];
    for (int i = n - 1; i > r_id; i--) {
        items[i].p -= items[i - 1].p;
    }
    for (int i = r_id; i < n; i++) 
        if (remain >= items[i].p) 
        {
            remain -= items[i].p;
            res.push_back(items[i].idx);
        }
    return res;
}

signed main()
{
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccsbjl3i.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccHQthJ8.o:festival.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccsbjl3i.o: in function `main':
grader.cpp:(.text.startup+0x232): undefined reference to `max_coupons(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status