| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1249388 | oscar1f | Souvenirs (IOI25_souvenirs) | C++20 | 0 ms | 0 KiB |
#include "souvenirs.h"
#include <utility>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct info {
vector<ll> liste;
ll total;
};
const ll TAILLE_MAX=100+5;
/*ll vraiNbAppel[TAILLE_MAX];
ll vraiVal[TAILLE_MAX];
ll vraiN;*/
ll nbAppel[TAILLE_MAX];
ll val[TAILLE_MAX];
ll nbVal,premIncon,nbReq;
vector<info> enCours;
/*pair<vector<ll>,ll> transaction(ll M) {
vector<ll> vraiAchat;
for (ll i=0;i<vraiN;i++) {
if (M>=vraiVal[i]) {
M-=vraiVal[i];
vraiAchat.push_back(i);
vraiNbAppel[i]++;
}
}
if (vraiAchat.empty()) {
cout<<-1<<endl;
}
return {vraiAchat,M};
}*/
info filtre(info anci) {
info nouv={{},anci.total};
for (ll i:anci.liste) {
if (val[i]==0) {
nouv.liste.push_back(i);
}
else {
nouv.total-=val[i];
}
}
return nouv;
}
info poseQuest(ll quest) {
//nbReq++;
auto ans=transaction(quest);
//cout<<'?'<<quest<<" !"<<quest-ans.second<<" : ";
for (ll i:ans.first) {
nbAppel[i]++;
//cout<<i<<" ";
}
//cout<<endl;
return filtre({ans.first,quest-ans.second});
}
void afficher(info nouv) {
return;
cout<<nouv.total<<" : ";
for (ll i:nouv.liste) {
cout<<i<<" ";
}
cout<<endl;
}
void buy_souvenirs(int N,ll P0) {
nbVal=N;
val[0]=P0;
while (premIncon<nbVal) {
if (val[premIncon]!=0) {
premIncon++;
}
else if (enCours.empty()) {
info nouv=poseQuest(val[premIncon-1]-1);
afficher(nouv);
enCours.push_back(nouv);
}
else {
info cour=filtre(enCours.back());
//cout<<"###";afficher(cour);
if (cour.liste.empty()) {
enCours.pop_back();
}
else if ((ll)cour.liste.size()==1) {
val[cour.liste[0]]=cour.total;
//cout<<"!!!"<<cour.liste[0]<<" "<<cour.total<<endl;
enCours.pop_back();
}
else {
ll quest=cour.total/cour.liste.size();
//cout<<quest<<" ";
for (ll i=0;i<cour.liste.back();i++) {
if (val[i]!=0 && val[i]<=quest) {
quest=val[i]-1;
}
}
//cout<<quest<<endl;
info nouv=poseQuest(quest);
afficher(nouv);
enCours.push_back(nouv);
}
}
}
/*for (ll i=0;i<nbVal;i++) {
cout<<val[i]<<" ";
}
cout<<endl;*/
for (ll i=0;i<nbVal;i++) {
while (nbAppel[i]<i) {
transaction(val[i]);
nbAppel[i]++;
}
}
}
/*void grader() {
cin>>vraiN;
for (int i=0;i<vraiN;i++) {
cin>>vraiVal[i];
}
buy_souvenirs(vraiN,vraiVal[0]);
for (int i=0;i<vraiN;i++) {
cout<<vraiNbAppel[i]<<" ";
}
cout<<endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
grader();
}*/