Submission #1258156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258156		ro9669	Souvenirs (IOI25_souvenirs)	C++20	22 / 100	0 ms	424 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(int x){
    return (1ll * x * (x + 1)) / 2;
}

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

void buy_souvenirs(int n , ll p0){
    set<int> st;
    P[0] = p0;
    st.insert(0);
    int total = 1;
    while (st.empty() == 0 && total < n){
        auto it = st.begin();
        int pos = *it;
        st.erase(it);
        ll val = P[pos] - 1;
        if (pos != n - 1){
            while (total < n){
                vll tmp = transaction(val);
                for (int id : tmp.fi) cnt[id]++;
                val -= tmp.se; tmp.se = val;
                vector<int> lis_id;
                for (int id : tmp.fi){
                    if (P[id] == 0){
                        lis_id.push_back(id);
                    }
                    tmp.se -= P[id];
                }
                tmp.fi = lis_id;
                val = tmp.se;
                T.push_back(tmp);
                if (sz(tmp.fi) == 1){
                    int nxt_pos = tmp.fi[0];
                    if (P[nxt_pos] == 0){
                        P[nxt_pos] = val;
                        st.insert(nxt_pos);
                        val--;
                        total++;
                        if (nxt_pos == n - 1) break;
                    }
                    else{
                        break;
                    }
                }
                else{
                    val = (val - f(sz(tmp.fi)) + sz(tmp.fi) - 1) / sz(tmp.fi) + sz(tmp.fi) - 1;
                }
            }
        }
        for (int i = sz(T) - 1 ; i >= 0 ; i--){
            vll tmp = T[i];
            ll val = tmp.se;
            int num = sz(tmp.fi);
            int nxt_pos = -1;
            for (int id : tmp.fi){
                if (P[id] != 0){
                    num--;
                    val -= P[id];
                }
                else{
                    nxt_pos = id;
                }
            }
            if (num == 1 && P[nxt_pos] == 0){
                st.insert(nxt_pos);
                P[nxt_pos] = val;
                total++;
            }
        }
    }
    while (true){
        ll val = 0;
        for (int i = 0 ; i < n ; i++){
            if (cnt[i] < i){
                cnt[i]++;
                val += P[i];
            }
        }
        if (val == 0) break;
        transaction(val);
    }
    //for (int i = 0 ; i < n ; i++) cout << cnt[i] << " ";
}

// int main(){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//     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: 0 / 3
• Subtask 3: 0 / 14
• Subtask 4: 18 / 18
• Subtask 5: 0 / 28
• Subtask 6: 0 / 33