Submission #1326057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326057		shirokito	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	404 KiB

souvenirs

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

#define UP1(i, n) for (int i = 0; i < (n); i++)
#define UP2(i, a, b) for (int i = (a); i <= (b); i++)
#define UP3(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define DN1(i, n) for (int i = (n) - 1; i >= 0; i--)
#define DN2(i, a, b) for (int i = (a); i >= (b); i--)
#define DN3(i, a, b, c) for (int i = (a); i >= (b); i -= (c))
#define FOR_IMPL(_1, _2, _3, _4, NAME, ...) NAME
#define FOR_UP(...) FOR_IMPL(__VA_ARGS__, UP3, UP2, UP1) (__VA_ARGS__)
#define FOR_DN(...) FOR_IMPL(__VA_ARGS__, DN3, DN2, DN1) (__VA_ARGS__)

#define POPCOUNT(n) __builtin_popcountll(n)
#define CLZ(n) __builtin_clzll(n)
#define CTZ(n) __builtin_ctzll(n)
#define LOG(n) __lg(n)
#define BIT(n, i) (((n) >> (i)) & 1LL)
#define FLIP(n, i) ((n) ^ (1LL << (i)))
#define ON(n, i) ((n) | (1LL << (i)))
#define OFF(n, i) ((n) & ~(1LL << (i)))

#define all(x) (x).begin(), (x).end()
#define len(x) (int)x.size()

#define fi first
#define se second

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;

#if __cplusplus <= 201402L
template <typename T> T gcd(T a, T b) { 
    return __gcd(a, b); 
}
template <typename T> T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}
#endif

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
    return uniform_int_distribution<long long>(l, r)(rng);  
}  

template <class T> void remove_duplicate(vector<T> &v) {
    sort(v.begin(), v.end()); 
    v.resize(unique(v.begin(), v.end()) - v.begin());
} 

template <class T> bool maximize(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <class T> bool minimize(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}  

const int MAXN = 100 + 24;

int n, cnt[MAXN]; ll p[MAXN];
bool found[MAXN];

void calc(ll x) {
    // cout << x << '\n';
    auto [ids, rem] = transaction(x);

    // FOR_UP (i, 1, n - 1) cout << p[i] << " \n" [i == n - 1];
    // FOR_UP (i, 1, n - 1) cout << found[i] << " \n" [i == n - 1];
    // for (int i: ids) cout << i << ' '; cout << '\n';

    for (int i: ids) cnt[i]++;

    ll sum = x - rem;

    while (found[ids.back()]) {
        int k = ids.back(); ids.pop_back();
        sum -= p[k];
    }

    while (len(ids) > 1) {
        calc(sum / len(ids));
        while (found[ids.back()]) {
            int k = ids.back(); ids.pop_back();
            sum -= p[k];
        }
    }

    if (len(ids)) {
        int i = ids[0];
        p[i] = sum; found[i] = 1;
        if (i < n - 1 && !found[i + 1]) calc(p[ids[0]] - 1);
    }
}

void buy_souvenirs(int n_, ll P0) {
    n = n_; p[0] = P0;
    
    calc(P0 - 1);

    // FOR_UP (i, 1, n - 1) cout << found[i] << " \n" [i == n - 1];
    // FOR_UP (i, 1, n - 1) cout << p[i] << " \n" [i == n - 1];
    
    FOR_UP (i, 1, n - 1) {
        while (cnt[i] != i) transaction(p[i]), cnt[i]++;
    }
}

• 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