#include "souvenirs.h"
#include <utility>
#include <vector>
#define ll long long
#define f first
#define s second
using namespace std;
void findRec(ll num,pair<vector<int>, long long> res, vector <ll> &p, int N, int &knwn){
if(res.first.size() == 1){
p[res.first[0]] = num - res.second;
if(res.first[0] == knwn - 1){
knwn = res.first[0];
return;
}
findRec(num - res.second - 1,transaction(num - res.second - 1), p, N, knwn);
knwn = res.first[0];
return;
}
while(true){
ll sum = 0;
for(int i = 0; i < res.first.size(); i++){
if(res.first[i] >= knwn){
sum += p[res.first[i]];
}
}
ll x = 0;
if(res.first[1] >= knwn){
p[res.first[0]] = num - sum;
knwn = res.first[0];
if(res.first[0] == res.first[1] - 1 || res.first[0] + 1 >= knwn){
break;
}
x = num - sum;
findRec(x,transaction(x - 1),p,N,knwn);
break;
}
x = (num - res.second - sum) / 2;
findRec(x,transaction(x),p,N,knwn);
}
}
void buy_souvenirs(int N, long long P0) {
pair<vector<int>, long long> res = transaction(P0 - 1);
vector <ll> p(N + 1),ws(N + 1);
for(int i = 0; i <= N; i++){
p[i] = 0;
}
findRec(P0 - 1,res,p,N,N);
return;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |