Submission #1250939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250939		haiphong5g0	Souvenirs (IOI25_souvenirs)	C++20	39 / 100	12 ms	812 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
#define task "TEST"
#define task2 "A"
#define pl pair<ll, ll>
#define pf push_front
#define pb push_back
#define pob pop_back
#define pof pop_front
#define mp make_pair
#define fi first
#define se second
#define FOR(i, a, b, c) for (int i=a; i<=b; i+=c)
#define FORE(i, a, b, c) for (int i=a; i>=b; i+=c)
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int Mod = 998244353;
const int maxn = 1e3;
const ll Inf = 1e16;
pair<vector<int>, ll> res;
ll P[maxn+1], num[maxn+1], n, A[maxn+1];
vector<pair<vector<int>, ll> > knowledge;
/*pair<vector<int>, ll> transaction(ll val){
    vector<int> a; a.clear();
    ll sum = val;
    FOR(i, 0, n-1, 1) {
        if (sum >= A[i]) {
            a.pb(i); sum -= A[i];
        }
    }
    return mp(a, sum);
}*/
void Fix(pair<vector<int>, ll>& know) {
    FOR(i, 0, (ll)know.fi.size()-1, 1) {
        ll p = know.fi[i];
        if (P[p] == 0) continue;
        know.fi.erase(know.fi.begin() + i);
        know.se -= P[p]; i--;
    }
}
void Add(ll val) {
    //cerr << val << " ";
    res = transaction(val);
    for (auto p : res.fi) num[p]++;
    res.se = val - res.se;
    Fix(res); knowledge.pb(res);
}
void Sub6(ll n) {
    ll val = P[0] - 1;
    while (true) {
        Add(val);
        if (res.fi.size() == 1) P[res.fi[0]] = res.se;
        if (P[n-1] != 0) break;
        if (res.fi.size() != 1) val = res.se / res.fi.size();
        else val = P[res.fi[0]] - 1;
    }
    bool ck = 0; ck = 1;
    FOR(i, 1, n-1, 1) if (P[i] == 0) ck = 0;
    while (!ck) {
        FOR(i, 0, (ll)knowledge.size()-1, 1) {
            pair<vector<int>, ll> know = knowledge[i];
            Fix(know);
            if (know.fi.size() > 1) {
                FOR(i, 0, know.fi.size()-1, 1)
                    if (num[know.fi[i]] >= know.fi[i]) continue;
                Add(know.se/know.fi.size());
            }
            else if (know.fi.size() == 1) {
                ll a = know.fi[0];
                P[a] = know.se;
            }
            if (know.fi.size() <= 1) knowledge.erase(knowledge.begin() + i), i--;
        }
        ck = 1;
        FOR(i, 1, n-1, 1) {
            if (P[i] != 0) continue;
            ck = 0;
            if (P[i-1] != 0 and num[i] < i) Add(P[i-1]-1);
        }
    }
    FOR(i, 1, n-1, 1) FOR(j, num[i], i-1, 1)
        Add(P[i]);
}
void buy_souvenirs(int n, long long P0) {
    P[0] = P0; Sub6(n);
}
/*int main() {
    cin >> n;
    FOR(i, 0, n-1, 1) cin >> A[i];
    buy_souvenirs(n, A[0]);
    FOR(i, 0, n-1, 1) cerr << num[i] << " ";
}*/

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