Submission #1312386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312386		saayan007	Souvenirs (IOI25_souvenirs)	C++20	7 / 100	13 ms	400 KiB

souvenirs

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

// #include "atcoder/"
// using namespace atcoder;

using ll = long long;
using vi = vector<int>;
using dt = pair<vector<int>, ll>;

#define eb emplace_back
#define fr first
#define sc second
#define mp make_pair

pair<vector<int>, ll> qry(ll M) {
    // printf("querying %lld\n", M);
    return transaction(M);
}

void buy_souvenirs(int n, long long m) {
    dt a[n];
    ll b[n];
    b[1] = m - 1;
    a[1] = qry(b[1]);
    for(int i = 2; i < n; ++i) {
        b[i] = (b[i - 1] - a[i - 1].sc + (ll)(a[i - 1].fr.size()) - 1) / ((ll)(a[i - 1].fr.size())) - 1;
        // if(a[i - 1].fr.size() == 1) --b[i];
        a[i] = qry(b[i]);
    }
    int p[n];
    p[0] = m;
    p[n - 1] = b[n - 1] - a[n - 1].sc;
    for(int i = n - 2; i > 0; --i) {
        vi v = a[i].fr;
        ll r = a[i].sc;
        ll c = b[i];
        p[i] = c - r;
        for(int x : v) {
            if(x != i) {
                p[i] -= p[x];
            }
        }
    }
    int cnt[n] = {};
    for(int i = 1; i < n; ++i) {
        for(int x : a[i].fr) ++cnt[x];
    }
    // for(int v : cnt) printf("%d ", v);
    // printf("\n");
    for(int i = 1; i < n; ++i) {
        while(cnt[i] < i) {
            qry(p[i]);
            ++cnt[i];
        }
    }
}

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