| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1341845 | KasymK | Souvenirs (IOI25_souvenirs) | C++20 | 0 ms | 0 KiB |
#include "bits/stdc++.h"
#include "grader.cpp"
// #include "souvenirs.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
#define mm make_pair
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
using node=pair<vector<int>, ll>;
const int MAX=105;
bool vis[MAX];
int cnt[MAX], n;
ll p[MAX];
void calc(ll M){
node P=transaction(M);
vector<int> v=P.ff;
ll sum=M-P.ss; // sum of selected indices, sum of p[s1]+p[s2]+...+p[sn]
tr(it, v)
cnt[*it]++;
while((int)v.size()>1){
if(vis[v.back()]){
sum-=p[v.back()];
v.pop_back();
continue;
}
calc(sum/(int)v.size());
}
vis[v[0]]=1, p[v[0]]=sum;
for(int i = v[0]+1; i < n; ++i)
if(!vis[i])
calc(p[i-1]-1);
}
void buy_souvenirs(int nn, ll p0){
n=nn;
vis[0]=1, p[0]=p0;
calc(p0-1);
for(int i = 0; i < n; ++i)
while(cnt[i]<i){
assert(p[i]>0);
node P=transaction(p[i]);
assert(P.ff[0]==i and P.ss==0);
cnt[i]++;
}
return;
}