#include "souvenirs.h" #include <utility> #include <vector> #include <cmath> #include <cstdlib> #include <unordered_set> #include <iostream> #include <queue> using namespace std; void buy_souvenirs(int N, long long P0) { unordered_set<long long> visited; vector<pair<unordered_set<int>, long long>> sums; int purchases[105] = {0,}; pair<vector<int>, long long> res = transaction(P0-1); visited.insert(P0-1); ////cout<<.+ unordered_set<int> res2; for (auto i:res.first) {res2.insert(i); purchases[i]++;} // for (int i = 0; i < N; i++) { // ////cout<<.+ // } ////cout<<.+ sums.push_back(make_pair(res2, P0-1-res.second)); ////cout<<.+ // for (auto j:sums) { // for (auto k:j.first) ////cout<<.+ // ////cout<<.+ // } ////cout<<.+ long long price = -1; // for (int __ = 0; __ < 40; __++) { unordered_set<int> visitedsums; queue<int> transactions; transactions.push(P0-1); while (1) { for (int i = sums.size()-1; i >= 0; i--) { if (visitedsums.find(i) != visitedsums.end()) continue; visitedsums.insert(i); // ////cout<<.+ unordered_set<int> s; for (auto i:sums) { if (i.first.size() == 1) s.insert(*i.first.begin()); } // for (int p = 0; p < N; p++) { // //cout<<.+ // } //cout<<.+ // //cout<<.+ // //cout<<.+ // //cout<<.+ //cout<<.+ if (s.size() >= N-1) break; // flag = false; // long long x = ceil((long double)sums[i].second/(long double)sums[i].first.size())-1; long long x = ceil((long double)(2*sums[i].second+sums[i].first.size()*(sums[i].first.size()-1))/(long double)(sums[i].first.size()*2))-1; if (price == -1) { for (auto j:sums) { // ////cout<<.+ if (j.first.size() == 1) { // ////cout<<.+ if (*j.first.begin() == N-1) price = j.second; } } } // bool flag = true; // for (int _ = 0; _ < 100; _++) { while (visited.find(x) != visited.end()) x--; // x--; // } // if (flag) { // sums.erase(sums.begin()+i); // } // ////cout<<.+ // ////cout<<.+ // if (x <= 0 || (price != -1 && x < price)) { // // if (purchases[N-1] >= N-1) continue; // long long a = transactions.front(); // transactions.pop(); // long long b = transactions.front(); // transactions.pop(); // //cout<<.+ // x = ((a+b)/2+rand()%300000)%(P0-1); // } // if (x <= 0) break; pair<vector<int>, long long> res3 = transaction(x); // if (x < 0) return; visited.insert(x); transactions.push(x); ////cout<<.+ ////cout<<.+ unordered_set<int> res4; for (auto j:res3.first) {res4.insert(j); purchases[j]++;} sums.push_back(make_pair(res4, x-res3.second)); ////cout<<.+ // for (auto j:sums) { // if (j.first.size() == 0) continue; // for (auto k:j.first) ////cout<<.+ // ////cout<<.+ // } ////cout<<.+ for (int j = 0; j < sums.size(); j++) { for (int k = 0; k < sums.size(); k++) { if (j == k) continue; if (sums[j].first.size() == 1) continue; bool flag2 = true; for (auto l:sums[k].first) { if (sums[j].first.find(l) == sums[j].first.end()) { flag2 = false; break; } } if (flag2) { for (auto l:sums[k].first) { sums[j].first.erase(l); } sums[j].second -= sums[k].second; } } } // if (i == 0) { // long long x = (sums.front().second+sums[1].second)/2; // while (visited.find(x) != visited.end()) x--; // // x--; // // } // // if (flag) { // // sums.erase(sums.begin()+i); // // } // // ////cout<<.+ // // ////cout<<.+ // if (x <= 0) break; // if (price != -1 && x < price) break; // pair<vector<int>, long long> res3 = transaction(x); // // if (x < 0) return; // visited.insert(x); // ////cout<<.+ // for (int j = 0; j < N; j++) { // ////cout<<.+ // } // ////cout<<.+ // unordered_set<int> res4; // for (auto j:res3.first) {res4.insert(j); purchases[j]++;} // sums.push_back(make_pair(res4, x-res3.second)); // } } bool flag3 = true; for (int i = 1; i < N; i++) { if (purchases[i] != i) {flag3 = false; break;} } if (flag3) return; // break; unordered_set<int> s; for (auto i:sums) { if (i.first.size() == 1) s.insert(*i.first.begin()); } // ////cout<<.+ if (s.size() >= N-1) break; } //cout<<.+ ////cout<<.+ ////cout<<.+ // for (auto j:sums) { // for (auto k:j.first) ////cout<<.+ // ////cout<<.+ // } ////cout<<.+ for (int i = 1; i < N; i++) { ////cout<<.+ if (purchases[i] == i) continue; long long price; ////cout<<.+ for (auto j:sums) { ////cout<<.+ if (j.first.size() == 1) { // ////cout<<.+ if (*j.first.begin() == i) price = j.second; } } ////cout<<.+ for (int _ = 0; _ < i-purchases[i]; _++) { transaction(price); ////cout<<.+ } } ////cout<<.+ return; }