Submission #1249859

#TimeUsernameProblemLanguageResultExecution timeMemory
1249859canadavid1Souvenirs (IOI25_souvenirs)C++20
21 / 100
12 ms412 KiB
#include "souvenirs.h" #include <iostream> /* have to query > P0-N for first N=3: query p-1 only 1: know price, ans that-1 twice both: know sum, ans half (round down) query p-1 only 1: know price. Continue more than 1 (ct): querying with val/ct must work if find Plast: query doubling the rest every time (start with rest=Plast), Plast+Plast*2**N at most one new each time. how to find Plast: query minimum allowed value every time if sum of k numbers are S, query S/k st3: P[i+1] in {Pi-1,Pi-2} ans P[i-1]-1 if more than one: must be P[N-1] == 1 not adaptive (!) */ void buy_souvenirs(int N, long long P0) { // st3 std::vector<long long> P(N,0); std::vector<int> ct(N,0); P[0] = P0; auto test = [&](long long M){ auto[o,r] = transaction(M); for(auto i : o) ct[i]++; return std::pair{o,r}; }; for(int i = 1; i < N; i++) { if (P[i]) continue; auto[o,r] = test(P[i-1]-1); if (o.size() > 1 || r == 1) { P[i] = P[i-1]-2; if (o.size() > 1) {P[N-1] = 1;} } else { P[i] = P[i-1]-1; } } for(int i = 1; i < N; i++) { if(!P[i] && ct[i] < i) { std::cerr << "solver failure\n"; exit(5); } while(ct[i] < i) test(P[i]); } }
#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...