Submission #1260044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260044		ro9669	Souvenirs (IOI25_souvenirs)	C++20	39 / 100	12 ms	416 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
using namespace std;

typedef long long ll;
typedef pair<vector<int> , long long> vll;
const int maxN = 107;
const int maxM = 5007;

// int n;
// ll p[maxN];

// pair<vector<int> , ll> transaction(ll m){
// //    cout << "start : " << m << "\n";
//     vector<int> tmp;
//     for (int i = 0 ; i < n ; i++){
//         if (m >= p[i]){
//             m -= p[i];
//             tmp.push_back(i);
//         }
//     }
// //    for (int x : tmp) cout << x << " ";
// //    cout << "\n";
// //    cout << m << "\n";
// //    cout << "-------------------------\n";
//     return {tmp , m};
// }

ll f(ll x){
    return (1ll * x * (x + 1)) / 2;
}

ll P[maxN];
int cnt[maxN];
vector<vll> T;

void transformer(vll &X){
    vector<int> tmp;
    for (int id : X.fi){
        if (P[id] == 0){
            tmp.push_back(id);
        }
        else{
            X.se -= P[id];
        }
    }
    X.fi = tmp;
}

void buy_souvenirs(int n , ll p0){
    int total = 0;
    set<ll> A , B;
    P[0] = p0;
    total++;
    A.insert(P[0] - 1);
    while (total < n){
        while (total < n && sz(A) > 0){
            ll val = *prev(A.end());
            A.erase(prev(A.end()));
            B.insert(val);
            vll X = transaction(val);
            for (int id : X.fi) cnt[id]++;
            X.se = val - X.se;
            transformer(X);
            if (sz(X.fi) == 0) break;
            T.push_back(X);
            if (sz(X.fi) == 1){
                int pos = X.fi[0];
                P[pos] = X.se;
                total++;
                if (B.count(P[pos] - 1) == 0) A.insert(P[pos] - 1);
                break;
            }
            else{
                val = (X.se - f(sz(X.fi)) + sz(X.fi) - 1) / sz(X.fi) + sz(X.fi) - 1;
                if (B.count(val) == 0) A.insert(val);
            }
        }
        int numTest = 2;
        while (numTest--){
            for (int i = sz(T) - 1 ; i >= 0 ; i--){
                transformer(T[i]);
                vll X = T[i];
                if (sz(X.fi) == 0) continue;
                if (sz(X.fi) == 1){
                    int pos = X.fi[0];
                    P[pos] = X.se;
                    total++;
                }
                ll val = (X.se - f(sz(X.fi)) + sz(X.fi) - 1) / sz(X.fi) + sz(X.fi) - 1;
                if (B.count(val) == 0) A.insert(val);
            }
        }
    }
    for (int i = 0 ; i < n ; i++){
        for (int j = 0 ; j < i - cnt[i] ; j++) transaction(P[i]);
    }
    // cout << "---------\n";
    // cout << total << "\n";
    // for (int i = 0 ; i < n ; i++) cout << (cnt[i] <= i) << " ";
    // cout << "\n";
    // for (int i = 0 ; i < n ; i++) cout << P[i] << " ";
}

// int main(){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//     freopen("templete.inp" , "r" , stdin);
//     cin >> n;
//     for (int i = 0 ; i < n ; i++) cin >> p[i];
//     buy_souvenirs(n , p[0]);
//     return 0;
// }

• 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