Submission #1306051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306051		StefanSebez	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	14 ms	792 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=150,inf=1e9;
const ll INF=1e18;
int num[N],n;
ll val[N];
vector<pair<vector<int>,ll>>Qs;
ll Ask(ll x){
    //printf("%i\n",x);
    pair<vector<int>,ll>y=transaction(x);
    //int temp[n+10]={0};
    //for(auto i:y.fi)temp[i]=1;
    //for(int i=0;i<n;i++) printf("%i ",temp[i]);printf("\n");
    Qs.pb({y.fi,x-y.se});
    for(auto i:y.fi)num[i]++;
    return Qs.back().se;
}
ll Sum(int j){
    ll x=Qs[j].se;
    for(auto i:Qs[j].fi)if(val[i])x-=val[i];
    return x;
}
int Cnt(int j){
    int x=Qs[j].fi.size();
    for(auto i:Qs[j].fi)if(val[i])x--;
    return x;
}
int Mx(int j){
    int mx=0;
    for(auto i:Qs[j].fi)if(!val[i])mx=max(mx,i);
    return mx;
}

void Clear(){
    Qs.clear();
    for(int i=0;i<=n;i++)num[i]=val[i]=0;
    n=0;
}
void buy_souvenirs(int n1,ll P0){
    n=n1;
    Ask(P0-1);
    for(int I=n-1;I>=1;I--){
        //printf("* %i\n",I);
        ll mn=INF;int j=0;
        for(int i=0;i<Qs.size();i++)if(Cnt(i)!=0){
            ll x=Sum(i)/Cnt(i)-1;
            if(Mx(i)==I)x++;
            //printf("{%i %lld}\n",i,x);
            if(mn>x||(mn==x&&Cnt(i)<Cnt(j)))mn=x,j=i;
        }
        //printf("%i\n",j);
        while(!(Cnt(j)==1&&Mx(j)==I)){
            ll x=Sum(j)/Cnt(j)-1;
            if(Mx(j)==I)x++;
            Ask(x);
            j=Qs.size()-1;
        }
        val[I]=Sum(j);
    }
    //printf("dopuna\n");
    for(int i=1;i<n;i++){
        while(num[i]<i)Ask(val[i]);
    }

    Clear();
}

• 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