Submission #1276485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276485		mehrzad	Festival (IOI25_festival)	C++17	Compilation error	0 ms	0 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;

struct Coupon {
    int idx;          // original index
    long long price;  // P[i]
    int type;         // T[i]
};

static const long long INF = (1LL << 60);          // big enough (≈10^18)

// compute (cur - price) * type, but cap at INF
static long long apply(long long cur, long long price, int type) {
    if (cur >= INF) return INF;               // already "infinite"
    __int128 tmp = (__int128)cur - price;
    if (tmp < 0) return -1;                    // not enough tokens
    tmp *= type;
    if (tmp > INF) return INF;
    return (long long)tmp;
}

// comparator for coupons with type > 1
static bool cmp_mult(const Coupon& a, const Coupon& b) {
    // compare a.price * a.type / (a.type-1)  with  b.price * b.type / (b.type-1)
    __int128 left  = (__int128)a.price * a.type * (b.type - 1);
    __int128 right = (__int128)b.price * b.type * (a.type - 1);
    if (left != right) return left < right;
    // tie‑break – larger multiplier first (does not affect correctness)
    if (a.type != b.type) return a.type > b.type;
    return a.price < b.price;
}

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    int N = (int)P.size();
    vector<Coupon> mult;          // T > 1
    vector<Coupon> one;           // T == 1
    for (int i = 0; i < N; ++i) {
        Coupon c{ i, (long long)P[i], T[i] };
        if (T[i] == 1) one.push_back(c);
        else           mult.push_back(c);
    }

    sort(mult.begin(), mult.end(), cmp_mult);          // ascending key
    sort(one.begin(),  one.end(),
         [](const Coupon& a, const Coupon& b){ return a.price < b.price; });

    // concatenated list
    vector<Coupon> all;
    all.reserve(N);
    for (auto &c : mult) all.push_back(c);
    for (auto &c : one)  all.push_back(c);
    int M = (int)all.size();

    // DP tables
    vector<vector<long long>> dp(M + 1, vector<long long>(M + 1, -1));
    vector<vector<char>> take(M + 1, vector<char>(M + 1, 0));

    dp[0][0] = A;

    for (int i = 1; i <= M; ++i) {
        const Coupon &c = all[i - 1];
        for (int k = 0; k <= i; ++k) {
            long long best = dp[i - 1][k];   // skip
            char used = 0;

            if (k > 0) {
                long long prev = dp[i - 1][k - 1];
                if (prev >= 0 && prev >= c.price) {
                    long long after = apply(prev, c.price, c.type);
                    if (after > best) {
                        best = after;
                        used = 1;
                    }
                }
            }
            dp[i][k] = best;
            take[i][k] = used;
        }
    }

    // best achievable number of coupons
    int bestK = 0;
    for (int k = M; k >= 0; --k) {
        if (dp[M][k] >= 0) { bestK = k; break; }
    }

    // reconstruct the answer
    vector<int> answer;
    int i = M, k = bestK;
    while (i > 0 && k > 0) {
        if (take[i][k]) {
            answer.push_back(all[i - 1].idx);
            --k;
        }
        --i;
    }
    reverse(answer.begin(), answer.end());
    return answer;
}
", "grade": [0.0, 7.0, 0.0, 15.0, 0.0, 0.0, 0.0], "tokens": 40181}, {"code": "#include <bits/stdc++.h>
using namespace std;

struct Coupon {
    int idx;          // original index
    long long p;      // price
    int t;            // type (multiplier)
};

/*  comparison for coupons with T > 1:
    increasing K = p * t / (t-1)
    (compare a.p * a.t * (b.t-1)  with  b.p * b.t * (a.t-1) )
*/
bool cmpK(const Coupon& a, const Coupon& b) {
    // both a.t > 1 and b.t > 1
    __int128 left  = (__int128)a.p * a.t * (b.t - 1);
    __int128 right = (__int128)b.p * b.t * (a.t - 1);
    if (left != right) return left < right;
    // tie‑break – any deterministic rule is fine
    if (a.t != b.t) return a.t > b.t;        // larger multiplier first
    return a.p > b.p;                         // larger price first
}

/* ------------------------------------------------------------ */

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    const int N = (int)P.size();

    /* split coupons */
    vector<Coupon> pos, ones;
    for (int i = 0; i < N; ++i) {
        if (T[i] > 1)
            pos.push_back({i, P[i], T[i]});
        else
            ones.push_back({i, P[i], T[i]});   // T == 1
    }

    /* sort as proved in the analysis */
    sort(pos.begin(), pos.end(), cmpK);                 // increasing K
    sort(ones.begin(), ones.end(),
         [](const Coupon& a, const Coupon& b) {
             return a.p < b.p;                         // cheapest first
         });

    vector<Coupon> all;
    all.reserve(N);
    all.insert(all.end(), pos.begin(), pos.end());
    all.insert(all.end(), ones.begin(), ones.end());
    const int M = (int)all.size();                     // M == N

    /* DP */
    const __int128 INF = (__int128)1 << 120;           // huge enough

    vector<vector<__int128>> dp(M + 1, vector<__int128>(M + 1, -1));
    vector<vector<char>>   take(M + 1, vector<char>(M + 1, 0));

    dp[0][0] = (__int128)A;

    for (int i = 1; i <= M; ++i) {
        const Coupon& c = all[i - 1];
        dp[i][0] = dp[i - 1][0];
        take[i][0] = 0;
        for (int k = 1; k <= i; ++k) {
            /* skip */
            dp[i][k] = dp[i - 1][k];
            take[i][k] = 0;

            /* take */
            if (dp[i - 1][k - 1] != -1 && dp[i - 1][k - 1] >= c.p) {
                __int128 base = dp[i - 1][k - 1] - c.p;
                __int128 after;
                if (base > INF / c.t) after = INF;
                else after = base * (__int128)c.t;
                if (after > dp[i][k]) {
                    dp[i][k] = after;
                    take[i][k] = 1;
                }
            }
        }
    }

    /* best obtainable number of coupons */
    int best = 0;
    for (int k = M; k >= 0; --k) {
        if (dp[M][k] != -1) {
            best = k;
            break;
        }
    }

    /* reconstruction */
    vector<int> answer;
    int i = M, k = best;
    while (i > 0) {
        if (take[i][k]) {
            answer.push_back(all[i - 1].idx);
            --k;
        }
        --i;
    }
    reverse(answer.begin(), answer.end());
    return answer;
}

Compilation message (stderr)

festival.cpp:101:79: error: stray '#' in program
  101 | ", "grade": [0.0, 7.0, 0.0, 15.0, 0.0, 0.0, 0.0], "tokens": 40181}, {"code": "#include <bits/stdc++.h>
      |                                                                               ^
festival.cpp:101:1: error: expected unqualified-id before user-defined string literal
  101 | ", "grade": [0.0, 7.0, 0.0, 15.0, 0.0, 0.0, 0.0], "tokens": 40181}, {"code": "#include <bits/stdc++.h>
      | ^~~~~~~~~
festival.cpp:104:8: error: redefinition of 'struct Coupon'
  104 | struct Coupon {
      |        ^~~~~~
festival.cpp:5:8: note: previous definition of 'struct Coupon'
    5 | struct Coupon {
      |        ^~~~~~
festival.cpp: In function 'bool cmpK(const Coupon&, const Coupon&)':
festival.cpp:116:34: error: 'const struct Coupon' has no member named 'p'
  116 |     __int128 left  = (__int128)a.p * a.t * (b.t - 1);
      |                                  ^
festival.cpp:116:40: error: 'const struct Coupon' has no member named 't'
  116 |     __int128 left  = (__int128)a.p * a.t * (b.t - 1);
      |                                        ^
festival.cpp:116:47: error: 'const struct Coupon' has no member named 't'
  116 |     __int128 left  = (__int128)a.p * a.t * (b.t - 1);
      |                                               ^
festival.cpp:117:34: error: 'const struct Coupon' has no member named 'p'
  117 |     __int128 right = (__int128)b.p * b.t * (a.t - 1);
      |                                  ^
festival.cpp:117:40: error: 'const struct Coupon' has no member named 't'
  117 |     __int128 right = (__int128)b.p * b.t * (a.t - 1);
      |                                        ^
festival.cpp:117:47: error: 'const struct Coupon' has no member named 't'
  117 |     __int128 right = (__int128)b.p * b.t * (a.t - 1);
      |                                               ^
festival.cpp:120:11: error: 'const struct Coupon' has no member named 't'
  120 |     if (a.t != b.t) return a.t > b.t;        // larger multiplier first
      |           ^
festival.cpp:120:18: error: 'const struct Coupon' has no member named 't'
  120 |     if (a.t != b.t) return a.t > b.t;        // larger multiplier first
      |                  ^
festival.cpp:120:30: error: 'const struct Coupon' has no member named 't'
  120 |     if (a.t != b.t) return a.t > b.t;        // larger multiplier first
      |                              ^
festival.cpp:120:36: error: 'const struct Coupon' has no member named 't'
  120 |     if (a.t != b.t) return a.t > b.t;        // larger multiplier first
      |                                    ^
festival.cpp:121:14: error: 'const struct Coupon' has no member named 'p'
  121 |     return a.p > b.p;                         // larger price first
      |              ^
festival.cpp:121:20: error: 'const struct Coupon' has no member named 'p'
  121 |     return a.p > b.p;                         // larger price first
      |                    ^
festival.cpp: At global scope:
festival.cpp:126:13: error: redefinition of 'std::vector<int> max_coupons(int, std::vector<int>, std::vector<int>)'
  126 | vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
      |             ^~~~~~~~~~~
festival.cpp:34:13: note: 'std::vector<int> max_coupons(int, std::vector<int>, std::vector<int>)' previously defined here
   34 | vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
      |             ^~~~~~~~~~~
festival.cpp: In lambda function:
festival.cpp:142:23: error: 'const struct Coupon' has no member named 'p'
  142 |              return a.p < b.p;                         // cheapest first
      |                       ^
festival.cpp:142:29: error: 'const struct Coupon' has no member named 'p'
  142 |              return a.p < b.p;                         // cheapest first
      |                             ^
festival.cpp: In function 'std::vector<int> max_coupons(int, std::vector<int>, std::vector<int>)':
festival.cpp:169:65: error: 'const struct Coupon' has no member named 'p'
  169 |             if (dp[i - 1][k - 1] != -1 && dp[i - 1][k - 1] >= c.p) {
      |                                                                 ^
festival.cpp:170:54: error: 'const struct Coupon' has no member named 'p'
  170 |                 __int128 base = dp[i - 1][k - 1] - c.p;
      |                                                      ^
festival.cpp:172:36: error: 'const struct Coupon' has no member named 't'
  172 |                 if (base > INF / c.t) after = INF;
      |                                    ^
festival.cpp:173:49: error: 'const struct Coupon' has no member named 't'
  173 |                 else after = base * (__int128)c.t;
      |                                                 ^