제출 #1256770

#제출 시각아이디문제언어결과실행 시간메모리
1256770medmdgSouvenirs (IOI25_souvenirs)C++20
25 / 100
11 ms420 KiB
#include "souvenirs.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; void sub1(int N, long long P0) { pair<vector<int>, long long> res = transaction(P0-1); } void sub2(int N, ll P0){ for(int i=N-1;i>0;i--){ for(int j=N;j>i;j--){ transaction(i); } } } void sub3(int N,ll P0){ vector<ll> rem(N); for(int i=0;i<N;i++){ rem[i]=i; } ll cost=P0-1; for(int i=1;i<N;i++){ pair<vector<int>, long long> res =transaction(cost); for(auto x:res.first)rem[x]--; if(res.first.size()>1||res.second)cost--; while(rem[i]){ res=transaction(cost); for(auto x:res.first)rem[x]--; } cost--; } } void sub4(int N, long long P0) { pair<vector<int>, long long> res = transaction(P0-1); ll cost=P0-1-res.second; //cout<<"#"<<cost<<endl; if(res.first.size()>1) transaction(cost/2); else{ transaction(cost-1); transaction(cost-1); } } pair<vector<int>, long long> ask(ll cost,vector<ll> &v){ pair<vector<int>, long long> res = transaction(cost); for(auto x:res.first)v[x]--; return res; } void full(int N,ll P0){ vector<ll> rem(N); for(int i=0;i<N;i++){ rem[i]=i; } vector<ll> costs(N,0); costs[0]=P0; pair<vector<int>, long long> res; ll cost=P0; vector<pair<vector<int>, long long>> pre; map<ll,ll> vis; while(1){ cost--; pair<vector<int>, long long> res=ask(cost,rem); pre.push_back(res); vis[res.first[0]]=pre.size(); pre.back().second=cost-res.second; cost=cost-res.second; if(res.first[0]==N-1){ costs.back()=cost; break; } if(res.first.size()==1){ continue; }else{ cost+=res.first.size()-1; cost/=res.first.size(); } } for(int i=N-2;i>0;i--){ if(vis[i]){ pair<vector<int>, long long> res=pre[vis[i]-1]; cost=res.second; for(auto x:res.first)cost-=costs[x]; costs[i]=cost; continue; } ll nex=i-1; while(!vis[nex]){ nex--; } pair<vector<int>, long long> res=pre[vis[i]-1]; cost=res.second; ll cou=res.second; for(auto x:res.first){ if(costs[x])cou--; cost-=costs[x]; } cost+=cou-1; cost/=cou; cost--; res=ask(cost,rem); pre.push_back(res); vis[res.first[0]]=pre.size(); pre.back().second=cost-res.second; i++; continue; } for(int i=0;i<N;i++){ while(rem[i]>0){ rem[i]--; transaction(costs[i]); } } } void buy_souvenirs(int N, long long P0) { full(N,P0); }
#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...