| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1312137 | pedreitorzelda | Souvenirs (IOI25_souvenirs) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
//#define int long long
//vector<int>a;
//int n;
/*pair<vector<int>,int>transaction(int num){
vector<int>ans;
int og = num;
for(int i=0;i<n;i++){
if(num>=a[i]){
ans.push_back(i);
num-=a[i];
}
}//cout << " " << ans.size() << "::";
//for(auto it : ans)cout << it << " ";
//cout << "-- " << num << endl;
if(ans.empty()){
cout << og << " BAAAAAD - none " << num << endl;
_sleep(100);
}
return {ans,num};
}*/
pair<vector<int>,long long>transaction(long long cost);
void to_buy(long long ind,long long cost,vector<long long>&vals,vector<long long>&cant){
if(vals[ind]!=-1LL)return;
//cout << ind << "?";
pair<vector<long long>,long long>ans = transaction(cost);
for(auto it : ans.first)cant[it]++;
if(ans.first.empty()){
//cout << vals.size() <<" "<< vals[n-1] <<" " << ind << "- error- " << cost << endl;
//_sleep(100);
return;
}
if(ans.first.size()==1LL){
vals[ans.first[0]]=cost-ans.second;
//cout << "VALS::" <<ans.first[0] << " " << cost-ans.second << endl;
if(ans.first[0]<ind)to_buy(ind,vals[ans.first[0]]-1LL,vals,cant);
}else{
long long bef_ind = ind;
ind = ans.first[0];
reverse(ans.first.begin(),ans.first.end());
long long nxt = ans.second;
long long act_cant = ans.first.size();
for(auto it : ans.first){
if(it==ind)continue;
if(vals[it]==-1){
long long act_cost = (cost-nxt+act_cant-1LL)/act_cant-(act_cant)/2LL;
long long last_ind = it;
int count = 0;
while(last_ind>=0LL){
if(vals[last_ind]!=-1LL){
act_cost = min(act_cost,vals[last_ind]-count);
break;
}last_ind--;
count++;
}
//cout << ind << " " << cost << "-->" << it << " " << act_cost << endl;
to_buy(it,act_cost,vals,cant);
}
nxt+=vals[it];
act_cant--;
}vals[ind]=cost-nxt;
//cout << "VALS2::" << ind << " -- " << cost-nxt << '\n';
if(vals[bef_ind]==-1LL){
long long best_aprox = 0;
long long last_ind = bef_ind;
while(last_ind>=0LL){
if(vals[last_ind]!=-1LL){
best_aprox = vals[last_ind];
break;
}last_ind--;
}to_buy(bef_ind,best_aprox-1LL,vals,cant);
}
}return;
}
//int done = 0;
void buy_souvenirs(int N, long long P0){
vector<long long>vals(N,-1);
vector<long long>cant(N,0);
vals[0]=P0;
for(int i=1;i<N;i++){
if(vals[i]==-1){
to_buy(i,vals[i-1]-1LL,vals,cant);
}
}
for(int i=0;i<N;i++){
if(cant[i]>i)cout << "BBBBAAAAAAAAD" << "- big"<<i << endl;
else{
//if(vals[i]!=a[i])cout << "BAD-error" << endl;
while(cant[i]<i){
transaction(vals[i]);
cant[i]++;
}
}
}//done++;
return;
}
/*
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
int MAXI = 10;
while(t--){
n = 3;
//cout << n << '\n';
a.resize(n);
for(int i=0;i<n;i++){
a[i] = rand()%MAXI;
}
sort(a.begin(),a.end());
auto it = unique(a.begin(),a.end());
int x = 0;
while(it!=a.end()){
(*it) = MAXI+x;
x++;
it++;
}
sort(a.begin(),a.end(),greater<int>());
//for(int i=0;i<n;i++)cout << a[i] << " ";
//cout << '\n';
buy_souvenirs(n,a[0]);
a.clear();
}cout << done << endl;
return 0;
}*/