#include "souvenirs.h"
#include <vector>
#include <utility>
void buy_souvenirs(int N, long long P0) {
// First transaction – use the largest admissible M
long long M0 = P0 - 1; // P0 > M0 ≥ P[N‑1] is guaranteed
auto res0 = transaction(M0);
const std::vector<int> &L0 = res0.first;
long long R0 = res0.second;
bool have1 = false, have2 = false;
for (int t : L0) {
if (t == 1) have1 = true;
if (t == 2) have2 = true;
}
// ------------------------------------------------------------
// Case 1 : only type 1 was bought -> we know P1
if (have1 && !have2) {
long long P1 = M0 - R0; // price of type 1
long long M1 = P1 - 1; // lies in [P2 , P1-1]
auto res1 = transaction(M1);
long long P2 = M1 - res1.second; // price of type 2
// we already have: 1 × type1 (first transaction)
// 1 × type2 (second transaction)
// need one more type2
transaction(P2); // buys the second type2
}
// ------------------------------------------------------------
// Case 2 : both types were bought -> we know P1+P2
else if (have1 && have2) {
long long sum = M0 - R0; // P1 + P2
long long M2 = sum / 2; // floor((P1+P2)/2), satisfies P2 ≤ M2 < P1
auto res2 = transaction(M2);
long long P2 = M2 - res2.second; // price of type 2 (computed for completeness)
// first transaction gave 1×type1 and 1×type2,
// second transaction gives the missing second type2.
// Required numbers are already satisfied; we stop here.
}
// ------------------------------------------------------------
// The following branch cannot happen for M0 = P0-1, but is kept for safety.
else if (!have1 && have2) {
// (Only type 2 was bought – would mean M0 < P1, which never occurs here.)
// We find P1 by binary search, then finish the required purchases.
// This code would never be reached with the chosen M0.
long long P2 = M0 - R0;
long long lo = P2, hi = P0 - 1;
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
auto r = transaction(mid);
bool only2 = (r.first.size() == 1 && r.first[0] == 2);
if (only2) lo = mid + 1;
else hi = mid;
}
long long P1 = lo; // now we know P1
transaction(P1); // buy the missing type1
transaction(P2); // buy the second type2
}
// No other situation can occur for the given constraints.
}
