# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1249514 | FernandoJC07 | Souvenirs (IOI25_souvenirs) | C++20 | 0 ms | 0 KiB |
#include <vector>
#include "souvenirs.h"
#define ff first
#define ss second
#define ll long long
#define vi vector<long long>
void buy_souvenirs(int N, ll P0){
if(N==2) {transaction(P0-1); return;}
if(N==3) {
auto x = transaction(P0-1);
if(x.ff.size() == 1){
ll val = P0-1-x.ss;
transaction(val-1);
transaction(val-1);
}
else {
ll val = (P0-1-x.ss);
val += (2-val%2)%2;
val/=2;
transaction(val-1);
}
return;
}
vi cnt(N, 0), val(N);
val[0] = P0;
for(int i = 1; i<N; ++i){
auto x = transaction(val[i-1]-1);
for(int y: x.ff) cnt[y]++;
if(x.ff.size() == 1) val[i] = val[i-1]-1-x.ss;
else val[i] = val[i-1]-2;
}
for(int i = 1; i<N; ++i) while(cnt[i]<i) {transaction(val[i]); cnt[i]++;}
}