제출 #1276476

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276476		mehrzad	Festival (IOI25_festival)	C++17	컴파일 에러	0 ms	0 KiB

festival

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

struct Coupon {
    int idx;          // original index
    long long P;      // price
    int T;            // multiplier (1..4)
};

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    int N = (int)P.size();
    vector<Coupon> coupons;
    coupons.reserve(N);
    for (int i = 0; i < N; ++i) {
        coupons.push_back({i, (long long)P[i], T[i]});
    }

    /*  Sort by descending v = P * T / (T-1).
        T = 1 gives v = +infinity, therefore all T=1 coupons are placed
        before any T>1 coupon.  */
    auto cmp = [](const Coupon& a, const Coupon& b) {
        if (a.T == 1 && b.T != 1) return true;
        if (b.T == 1 && a.T != 1) return false;
        if (a.T == 1 && b.T == 1) return a.idx < b.idx;           // tie‑break
        // both T > 1 : compare a.P * a.T / (a.T-1)  vs  b.P * b.T / (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;                  // descending v
        return a.idx < b.idx;
    };
    sort(coupons.begin(), coupons.end(), cmp);

    int M = (int)coupons.size();
    const long long INF = (1LL << 60);   // large enough

    // dp[i][c] = minimal initial tokens needed after considering first i coupons
    //            and taking exactly c of them.
    vector<vector<long long>> dp(M + 1, vector<long long>(M + 1, INF));
    vector<vector<int>> prev_c(M + 1, vector<int>(M + 1, -1));
    vector<vector<char>> took(M + 1, vector<char>(M + 1, 0));

    dp[0][0] = 0;
    prev_c[0][0] = -1;

    for (int i = 0; i < M; ++i) {
        const Coupon& cur = coupons[i];
        for (int c = 0; c <= i; ++c) {
            if (dp[i][c] == INF) continue;

            // skip current coupon
            if (dp[i][c] < dp[i + 1][c]) {
                dp[i + 1][c] = dp[i][c];
                prev_c[i + 1][c] = c;
                took[i + 1][c] = 0;
            }

            // take current coupon (adds it at the front of the reverse order)
            long long new_need = cur.P + (dp[i][c] + cur.T - 1) / cur.T; // ceil division
            if (new_need < dp[i + 1][c + 1]) {
                dp[i + 1][c + 1] = new_need;
                prev_c[i + 1][c + 1] = c;
                took[i + 1][c + 1] = 1;
            }
        }
    }

    long long A_ll = (long long)A;
    int best = 0;
    for (int c = M; c >= 0; --c) {
        if (dp[M][c] <= A_ll) {
            best = c;
            break;
        }
    }

    vector<int> answer;
    if (best == 0) return answer;

    // reconstruct the chosen coupons; this yields the purchase order
    // (because we backtrack from the end of the descending‑v list).
    int i = M;
    int c = best;
    while (i > 0) {
        if (took[i][c]) {
            answer.push_back(coupons[i - 1].idx);
            c = prev_c[i][c];
        } else {
            c = prev_c[i][c];
        }
        --i;
    }
    // 'answer' already lists coupons in the order they should be bought.
    return answer;
}
", "grade": [0.0, 7.0, 0.0, 15.0, 0.0, 0.0, 0.0], "tokens": 46284}, {"code": "#include <bits/stdc++.h>
using namespace std;

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

struct Prev {
    int pi;      // previous i
    int pc;      // previous count
    bool took;   // was the coupon taken ?
};

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    int N = (int)P.size();
    vector<Coupon> cur(N);
    for (int i = 0; i < N; ++i) {
        cur[i] = {i, (long long)P[i], T[i]};
    }

    /* sort by decreasing ratio  (P*T)/(T-1),   T==1 => +infinity */
    auto cmp = [](const Coupon& a, const Coupon& b) {
        if (a.t == 1 && b.t == 1) return a.idx < b.idx;      // tie‑break
        if (a.t == 1) return true;                          // a has larger ratio
        if (b.t == 1) return false;
        // both T > 1
        long long left  = a.p * a.t * (b.t - 1);   // <= 12·10⁹, fits in 64 bit
        long long right = b.p * b.t * (a.t - 1);
        if (left != right) return left > right;   // larger ratio first
        return a.idx < b.idx;
    };
    sort(cur.begin(), cur.end(), cmp);   // decreasing ratio

    const long long INF = (1LL << 60);   // far bigger than any possible need

    // dp[i][c] = minimal need after first i coupons, having taken c of them
    vector<vector<long long>> dp(N + 1, vector<long long>(N + 1, INF));
    vector<vector<Prev>> pre(N + 1, vector<Prev>(N + 1, {-1, -1, false}));

    dp[0][0] = 0;
    for (int i = 0; i < N; ++i) {
        long long price = cur[i].p;
        int mult = cur[i].t;
        for (int c = 0; c <= i; ++c) {
            long long curNeed = dp[i][c];
            if (curNeed == INF) continue;

            // skip coupon i
            if (curNeed < dp[i + 1][c]) {
                dp[i + 1][c] = curNeed;
                pre[i + 1][c] = {i, c, false};
            }

            // take coupon i
            long long cand = price + ( (curNeed + mult - 1) / mult );
            if (cand < dp[i + 1][c + 1]) {
                dp[i + 1][c + 1] = cand;
                pre[i + 1][c + 1] = {i, c, true};
            }
        }
    }

    // find maximal feasible number of coupons
    int best_c = 0;
    for (int c = N; c >= 0; --c) {
        if (dp[N][c] <= (long long)A) {
            best_c = c;
            break;
        }
    }

    if (best_c == 0) return {};

    // reconstruct one optimal set (forward order = ascending ratio)
    vector<int> answer;
    int i = N, c = best_c;
    while (i > 0) {
        Prev p = pre[i][c];
        if (p.pi == -1) break;               // safety (should not happen)
        if (p.took) {
            answer.push_back(cur[i - 1].idx); // coupon i-1 was taken
        }
        i = p.pi;
        c = p.pc;
    }
    // answer already in forward (ascending‑ratio) order
    return answer;
}
", "grade": [0.0, 7.0, 0.0, 15.0, 0.0, 0.0, 0.0], "tokens": 39666}, {"code": "#include "festival.h"
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
using i128 = __int128_t;

struct Coupon {
    int idx;               // original index
    int64 P;               // price
    int T;                 // type
    i128 num;              // P * T   (for v = num / (T-1) )
    int64 den;             // T-1
    bool inf;              // true for T == 1   (v = +∞)
};

static i128 INF = ( (i128)1 << 60 );          // sufficiently large (≈10^18)

static i128 ceil_div(i128 a, int64 b) {
    return (a + b - 1) / b;
}

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
    int N = (int)P.size();
    vector<Coupon> coupons;
    coupons.reserve(N);
    for (int i = 0; i < N; ++i) {
        Coupon c;
        c.idx = i;
        c.P = P[i];
        c.T = T[i];
        if (c.T == 1) {
            c.inf = true;
            c.num = 0;
            c.den = 1;
        } else {
            c.inf = false;
            c.num = (i128)c.P * (i128)c.T;   // numerator of v
            c.den = c.T - 1;
        }
        coupons.push_back(c);
    }

    // sort by decreasing v (inf first)
    auto cmp = [](const Coupon& a, const Coupon& b) {
        if (a.inf != b.inf) return a.inf > b.inf;          // inf (T==1) is larger
        // compare a.num / a.den  >  b.num / b.den   ?
        // i.e. a.num * b.den > b.num * a.den
        i128 left = a.num * (i128)b.den;
        i128 right = b.num * (i128)a.den;
        if (left != right) return left > right;
        return a.idx < b.idx;               // tie‑break – deterministic
    };
    sort(coupons.begin(), coupons.end(), cmp);

    // DP[i][k] = minimal needed tokens before first i coupons,
    //            using exactly k of them.
    vector<vector<i128>> dp(N + 1, vector<i128>(N + 1, INF));
    vector<vector<char>> take(N + 1, vector<char>(N + 1, -1));
    vector<vector<int>> prevK(N + 1, vector<int>(N + 1, -1));

    dp[0][0] = 0;   // nothing needed before empty prefix

    for (int i = 0; i < N; ++i) {
        const Coupon& c = coupons[i];
        for (int k = 0; k <= i; ++k) {
            i128 cur = dp[i][k];
            if (cur == INF) continue;

            /* skip c */
            if (cur < dp[i + 1][k]) {
                dp[i + 1][k] = cur;
                take[i + 1][k] = 0;
                prevK[i + 1][k] = k;
            }

            /* take c (it becomes the last bought coupon) */
            i128 need = (i128)c.P + ceil_div(cur, c.T);
            if (need < dp[i + 1][k + 1]) {
                dp[i + 1][k + 1] = need;
                take[i + 1][k + 1] = 1;
                prevK[i + 1][k + 1] = k;
            }
        }
    }

    int bestK = 0;
    for (int k = N; k >= 0; --k) {
        if (dp[N][k] <= (i128)A) { bestK = k; break; }
    }

    // reconstruction
    vector<int> answer;
    int i = N, k = bestK;
    while (i > 0) {
        char wasTaken = take[i][k];
        int pk = prevK[i][k];
        if (wasTaken == 1) {
            answer.push_back(coupons[i - 1].idx);   // this coupon is taken
        }
        k = pk;
        --i;
    }
    // 'answer' was built while walking from the end of the list to the
    // beginning, i.e. in increasing v order – the exact purchase order.
    // No further reversal is necessary.

    return answer;        // may be empty
}

컴파일 시 표준 에러 (stderr) 메시지

festival.cpp:96:79: error: stray '#' in program
   96 | ", "grade": [0.0, 7.0, 0.0, 15.0, 0.0, 0.0, 0.0], "tokens": 46284}, {"code": "#include <bits/stdc++.h>
      |                                                                               ^
festival.cpp:186:79: error: stray '#' in program
  186 | ", "grade": [0.0, 7.0, 0.0, 15.0, 0.0, 0.0, 0.0], "tokens": 39666}, {"code": "#include "festival.h"
      |                                                                               ^
festival.cpp:96:1: error: expected unqualified-id before user-defined string literal
   96 | ", "grade": [0.0, 7.0, 0.0, 15.0, 0.0, 0.0, 0.0], "tokens": 46284}, {"code": "#include <bits/stdc++.h>
      | ^~~~~~~~~
festival.cpp:99:8: error: redefinition of 'struct Coupon'
   99 | struct Coupon {
      |        ^~~~~~
festival.cpp:5:8: note: previous definition of 'struct Coupon'
    5 | struct Coupon {
      |        ^~~~~~
festival.cpp:111:13: error: redefinition of 'std::vector<int> max_coupons(int, std::vector<int>, std::vector<int>)'
  111 | vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
      |             ^~~~~~~~~~~
festival.cpp:11:13: note: 'std::vector<int> max_coupons(int, std::vector<int>, std::vector<int>)' previously defined here
   11 | vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
      |             ^~~~~~~~~~~
festival.cpp: In lambda function:
festival.cpp:120:15: error: 'const struct Coupon' has no member named 't'
  120 |         if (a.t == 1 && b.t == 1) return a.idx < b.idx;      // tie‑break
      |               ^
festival.cpp:120:27: error: 'const struct Coupon' has no member named 't'
  120 |         if (a.t == 1 && b.t == 1) return a.idx < b.idx;      // tie‑break
      |                           ^
festival.cpp:121:15: error: 'const struct Coupon' has no member named 't'
  121 |         if (a.t == 1) return true;                          // a has larger ratio
      |               ^
festival.cpp:122:15: error: 'const struct Coupon' has no member named 't'
  122 |         if (b.t == 1) return false;
      |               ^
festival.cpp:124:29: error: 'const struct Coupon' has no member named 'p'
  124 |         long long left  = a.p * a.t * (b.t - 1);   // <= 12·10⁹, fits in 64 bit
      |                             ^
festival.cpp:124:35: error: 'const struct Coupon' has no member named 't'
  124 |         long long left  = a.p * a.t * (b.t - 1);   // <= 12·10⁹, fits in 64 bit
      |                                   ^
festival.cpp:124:42: error: 'const struct Coupon' has no member named 't'
  124 |         long long left  = a.p * a.t * (b.t - 1);   // <= 12·10⁹, fits in 64 bit
      |                                          ^
festival.cpp:125:29: error: 'const struct Coupon' has no member named 'p'
  125 |         long long right = b.p * b.t * (a.t - 1);
      |                             ^
festival.cpp:125:35: error: 'const struct Coupon' has no member named 't'
  125 |         long long right = b.p * b.t * (a.t - 1);
      |                                   ^
festival.cpp:125:42: error: 'const struct Coupon' has no member named 't'
  125 |         long long right = b.p * b.t * (a.t - 1);
      |                                          ^
festival.cpp: In function 'std::vector<int> max_coupons(int, std::vector<int>, std::vector<int>)':
festival.cpp:139:34: error: '__gnu_cxx::__alloc_traits<std::allocator<Coupon>, Coupon>::value_type' {aka 'struct Coupon'} has no member named 'p'
  139 |         long long price = cur[i].p;
      |                                  ^
festival.cpp:140:27: error: '__gnu_cxx::__alloc_traits<std::allocator<Coupon>, Coupon>::value_type' {aka 'struct Coupon'} has no member named 't'
  140 |         int mult = cur[i].t;
      |                           ^
festival.cpp: At global scope:
festival.cpp:186:1: error: expected unqualified-id before user-defined string literal
  186 | ", "grade": [0.0, 7.0, 0.0, 15.0, 0.0, 0.0, 0.0], "tokens": 39666}, {"code": "#include "festival.h"
      | ^~~~~~~~~
festival.cpp:193:8: error: redefinition of 'struct Coupon'
  193 | struct Coupon {
      |        ^~~~~~
festival.cpp:5:8: note: previous definition of 'struct Coupon'
    5 | struct Coupon {
      |        ^~~~~~
festival.cpp:208:13: error: redefinition of 'std::vector<int> max_coupons(int, std::vector<int>, std::vector<int>)'
  208 | vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
      |             ^~~~~~~~~~~
festival.cpp:11:13: note: 'std::vector<int> max_coupons(int, std::vector<int>, std::vector<int>)' previously defined here
   11 | vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
      |             ^~~~~~~~~~~
festival.cpp: In function 'std::vector<int> max_coupons(int, std::vector<int>, std::vector<int>)':
festival.cpp:218:15: error: 'struct Coupon' has no member named 'inf'
  218 |             c.inf = true;
      |               ^~~
festival.cpp:219:15: error: 'struct Coupon' has no member named 'num'
  219 |             c.num = 0;
      |               ^~~
festival.cpp:220:15: error: 'struct Coupon' has no member named 'den'
  220 |             c.den = 1;
      |               ^~~
festival.cpp:222:15: error: 'struct Coupon' has no member named 'inf'
  222 |             c.inf = false;
      |               ^~~
festival.cpp:223:15: error: 'struct Coupon' has no member named 'num'
  223 |             c.num = (i128)c.P * (i128)c.T;   // numerator of v
      |               ^~~
festival.cpp:224:15: error: 'struct Coupon' has no member named 'den'
  224 |             c.den = c.T - 1;
      |               ^~~
festival.cpp: In lambda function:
festival.cpp:231:15: error: 'const struct Coupon' has no member named 'inf'
  231 |         if (a.inf != b.inf) return a.inf > b.inf;          // inf (T==1) is larger
      |               ^~~
festival.cpp:231:24: error: 'const struct Coupon' has no member named 'inf'
  231 |         if (a.inf != b.inf) return a.inf > b.inf;          // inf (T==1) is larger
      |                        ^~~
festival.cpp:231:38: error: 'const struct Coupon' has no member named 'inf'
  231 |         if (a.inf != b.inf) return a.inf > b.inf;          // inf (T==1) is larger
      |                                      ^~~
festival.cpp:231:46: error: 'const struct Coupon' has no member named 'inf'
  231 |         if (a.inf != b.inf) return a.inf > b.inf;          // inf (T==1) is larger
      |                                              ^~~
festival.cpp:234:23: error: 'const struct Coupon' has no member named 'num'
  234 |         i128 left = a.num * (i128)b.den;
      |                       ^~~
festival.cpp:234:37: error: 'const struct Coupon' has no member named 'den'
  234 |         i128 left = a.num * (i128)b.den;
      |                                     ^~~
festival.cpp:235:24: error: 'const struct Coupon' has no member named 'num'
  235 |         i128 right = b.num * (i128)a.den;
      |                        ^~~
festival.cpp:235:38: error: 'const struct Coupon' has no member named 'den'
  235 |         i128 right = b.num * (i128)a.den;
      |                                      ^~~