Submission #1249391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249391		oscar1f	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	420 KiB

souvenirs

#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;
}

vector<ll> transfo(vector<int> v) {
    vector<ll> ans;
    for (int i:v) {
        ans.push_back(i);
    }
    return ans;
}

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({transfo(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();    
}*/

• Subtask 0: 0 / 0
• Subtask 1: 4 / 4
• Subtask 2: 3 / 3
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 28 / 28
• Subtask 6: 33 / 33