Submission #1249950

#TimeUsernameProblemLanguageResultExecution timeMemory
1249950tosivanmakSouvenirs (IOI25_souvenirs)C++20
25 / 100
12 ms416 KiB
#include<bits/stdc++.h> #include "souvenirs.h" using namespace std; #define ll long long pair<vector<int>,ll> starting[105]; ll sm[105]; ll cnt[105]; ll P[105]; void proc(pair<vector<int>,ll>pre, ll ending){ while(1){ ll S=pre.second; S--; S/=(ll)pre.first.size(); if(pre.first[0]==ending)break; pre=transaction(S); pre.second=S-pre.second; for(auto& u: pre.first){ cnt[u]++; } starting[pre.first[0]]=pre; } } void buy_souvenirs(int N, long long P0){ // std::pair<std::vector<int>, long long> transaction(long long M) for(int i=0;i<N+5;i++){ starting[i].first.clear(); starting[i].second=0; sm[i]=0; } P[0]=P0; ll asked=P0-1; pair<vector<int>,ll>req=transaction(P0-1); req.second=P0-1-req.second; starting[req.first[0]]=req; pair<vector<int>,ll>pre=req; for(int i=0;i<N+5;i++){ cnt[i]=0; } for(auto& u: pre.first){ cnt[u]++; } while(1){ ll S=pre.second; S--; S/=(ll)pre.first.size(); if(pre.first[0]==N-1)break; pre=transaction(S); pre.second=S-pre.second; for(auto& u: pre.first){ cnt[u]++; } starting[pre.first[0]]=pre; } for(int i=N-1;i>=0;i--){ if(starting[i].first.size()!=0){ P[i]=starting[i].second; for(int j=i-1;j>=0;j--){ if(starting[j].first.size()!=0){ if(starting[j].first.back()==i){ starting[j].second-=P[i]; starting[j].first.pop_back(); } } } } else{ for(int j=i-1;j>=0;j--){ if(starting[j].first.size()!=0){ proc(starting[j],i); break; } } } } for(int i=0;i<N;i++){ while(cnt[i]!=i){ transaction(P[i]); cnt[i]++; } } 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...