Submission #1276323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276323		otarius	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	14 ms	400 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 rngl(chrono::steady_clock::now().time_since_epoch().count());

// #define int long long
// #define int unsigned long long

// #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
// #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>

// const ll mod = 1e9 + 7;
// const ll mod = 998244353;

const ll inf = 1e9;
const ll biginf = 1e18;
// const int maxN;

// namespace {
// const int CALLS_CNT_LIMIT = 10'000;

// int calls_cnt;
// int N;
// std::vector<long long> P;
// std::vector<int> Q;

// void quit(const char* message) {
//   printf("%s\n", message);
//   exit(0);
// }
// } // namespace

// std::pair<std::vector<int>, long long> transaction(long long M) {
//   calls_cnt++;
//   if (calls_cnt > CALLS_CNT_LIMIT)
//     quit("Too many calls");
//   if (M >= P[0] || M < P[N - 1])
//     quit("Invalid argument");

//   std::vector<int> L;
//   long long R = M;
//   for (int i = 0; i < N; i++) {
//     if (R >= P[i]) {
//       R -= P[i];
//       Q[i]++;
//       L.push_back(i);
//     }
//   }
//   return {L, R};
// }

void buy_souvenirs(int n, ll p0) {
    ll ans[n], sum[n], cnt[n]{}; ans[0] = p0;
    for (int i = 1; i < n; i++) ans[i] = -1;

    vector<set<int>> eq(n);
    while (1) {
        bool f = 0;
        for (int i = 0; i < n; i++)
            f |= (ans[i] == -1);
        if (!f) break;

        f = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (i + 1 < n && ans[i] != -1 && ans[i + 1] == -1) {
                eq[i + 1].clear();
                pair<vector<int>, ll> ret = transaction(ans[i] - 1);
                for (int j : ret.ff) eq[i + 1].insert(j), cnt[j]++;
                sum[i + 1] = ans[i] - 1 - ret.sc;
                for (int j = 0; j < n; j++) {
                    if (ans[j] == -1) continue;
                    if (eq[i + 1].find(j) != eq[i + 1].end()) {
                        sum[i + 1] -= ans[j]; eq[i + 1].erase(j);
                    }
                } break;
            }

            if (eq[i].size() > 1) {
                pair<vector<int>, ll> ret = transaction(sum[i] / (int)eq[i].size());

                set<int> cur;
                for (int j : ret.ff) cur.insert(j), cnt[j]++;
                ll curs = sum[i] / (int)eq[i].size() - ret.sc;
                for (int j = 0; j < n; j++) {
                    if (ans[j] == -1) continue;
                    if (cur.find(j) != cur.end()) {
                        curs -= ans[j]; cur.erase(j);
                    }
                } eq[*cur.begin()] = cur; sum[*cur.begin()] = curs;
                break;
            }

            if (eq[i].size() == 1) {
                ans[i] = sum[i]; eq[i].clear();
                for (int j = 0; j < n; j++) {
                    if (eq[j].find(i) != eq[j].end()) {
                        sum[j] -= ans[i]; eq[j].erase(i);
                    }
                } break;
            }


        }
    }

    for (int i = 0; i < n; i++) {
        while (cnt[i] < i) transaction(ans[i]), cnt[i]++;
    }
}

// int main() {
//   assert(1 == scanf("%d", &N));
//   P.resize(N);
//   for (int i = 0; i < N; i++)
//     assert(1 == scanf("%lld", &P[i]));
//   fclose(stdin);

//   Q.assign(N, 0);
//   calls_cnt = 0;
//   buy_souvenirs(N, P[0]);
//   for (int i = 0; i < N; i++)
//     printf("%s%d", i ? " " : "", Q[i]);
//   printf("\n");
//   fclose(stdout);

//   return 0;
// }

• Subtask 0: 0 / 0
• Subtask 1: 4 / 4
• Subtask 2: 3 / 3
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 28 / 28
• Subtask 6: 33 / 33