Submission #1253986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253986		countless	Festival (IOI25_festival)	C++20	24 / 100	689 ms	9388 KiB

festival

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

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

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

    vector<int> o, t;
    for (int i = 0; i < N; i++) {
        if (T[i] == 1) o.emplace_back(i);
        else t.emplace_back(i);
    }

    sort(o.begin(), o.end(), [&](int i, int j) {
        return P[i] < P[j];
    });
    vector<ld> pref;
    for (auto &i : o) {
        if (pref.empty()) pref.emplace_back(P[i]);
        else pref.emplace_back(pref.back() + P[i]);
    }

    sort(t.begin(), t.end(), [&](int i, int j) {
        return P[i] < P[j];
    });

    int M = t.size();
    // we take some prefix of o and some prefix of t
    ld have = A;
    int best = upper_bound(pref.begin(), pref.end(), have) - pref.begin() - 1;
    int ind = -1, oth = upper_bound(pref.begin(), pref.end(), have) - pref.begin();
    cerr << best sp o.size() sp t.size() << endl;
    for (int i = 0; i < M; i++) {
        if (have < P[t[i]]) break;
        have = ld(2) * (have - P[t[i]]);
        if (i >= 32) cerr << have sp P[t[i]] << endl;
        if (have < 0) break;

        int cand = i + upper_bound(pref.begin(), pref.end(), have) - pref.begin() - 1;
        if (cand > best) {
            best = cand;
            ind = i;
            oth = upper_bound(pref.begin(), pref.end(), have) - pref.begin();
        }
    }

    vector<int> ans;
    if (ind == -1) {
        for (int i = 0; i < oth; i++) {
            ans.emplace_back(o[i]);
        }
    } else {
        for (int i = 0; i <= ind; i++) {
            ans.emplace_back(t[i]);
        }

        for (int i = 0; i < oth; i++) {
            ans.emplace_back(o[i]);
        }
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 27
• Subtask 6: 0 / 16
• Subtask 7: 0 / 18