# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1252778 | nickolasarapidis | Souvenirs (IOI25_souvenirs) | C++20 | 0 ms | 0 KiB |
#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
void buy_souvenirs(int N, long long P0){
pair<vector<int>, long long> a;
vector<int> cnt(N , 0);
long long lo = 1, up = P0;
for(int i = 1; i < N; i++){
long long l = lo, r = up;
while(l <= r){
int m = (l + r)/2;
a = transaction(m);
for(auto u : a.F){
cnt[u]++;
}
if(a.F.size() == 1 and a.F.back() == i){
for(int j = cnt[i]; j < i; j++){
a = transcation(m);
}
lo = m;
break;
}
else if(a.F.back() > i){
l = m + 1;
}
else{
r = m - 1;
}
}
}
}