#include "souvenirs.h" #include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++) #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--) #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++) #define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++) #define ALL(v) (v).begin(), (v).end() #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) using namespace std; void buy_souvenirs(int N, long long P0) { vector<long long> P(N), cnt(N); P[0] = P0; cnt[0] = 1; FOR(i, 1, N - 1) { if(P[i] != 0) { REP(j, i - cnt[i]) transaction(P[i]); } else { pair<vector<int>, long long> s = transaction(P[i - 1] - 1); if((int)s.first.size() == 1) { if(s.second == 0) P[i] = P[i - 1] - 1; else P[i] = P[i - 1] - 2; } else if((int)s.first.size() == 2) { P[i] = P[i - 1] - 2; if(i + 1 < N) P[i + 1] = 1; } else P[i] = max(1ll, P[i - 1] - 1); FORE(it, s.first) cnt[*it]++; if(P[i] != 0) REP(j, i - cnt[i]) transaction(P[i]); } } return; }