Submission #1260285

#TimeUsernameProblemLanguageResultExecution timeMemory
1260285sabamaku선물 (IOI25_souvenirs)C++20
0 / 100
0 ms400 KiB
#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, vector <ll> &ws){ for(int i = 0; i < res.first.size(); i++){ ws[res.first[i]]++; } 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,ws); 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; ll y = 0; if(res.first[1] >= knwn){ y = num - sum - res.second; p[res.first[0]] = y; if(res.first[0] == res.first[1] - 1 || res.first[0] + 1 >= knwn){ knwn = res.first[0]; break; } x = y; findRec(x,transaction(x - 1),p,N,knwn,ws); knwn = res.first[0]; break; } x = (num - res.second - sum) / 2; findRec(x,transaction(x),p,N,knwn,ws); } } 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; ws[i] = 0; } p[0] = P0; findRec(P0 - 1,res,p,N,N,ws); for(int i = 0; i < N; i++){ for(int j = 1; j <= i - ws[i]; j++){ transaction(p[i]); } } transaction(p[N - 1]); return; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...