Submission #1261527

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

souvenirs

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
std::pair<std::vector<int>, ll> transaction(ll M) ;
ll a[100];
void update(std::vector<int> ccc){
  for(int i=0;i<ccc.size();i++){
    a[ccc[i]]++;
  }
}
ll b[100];
int c[100];
std::map<ll,ll> cl;
std::map<ll,std::pair<std::vector<int>,ll> > pp;
std::vector <ll> k;
void query(ll P0,int n){
    std::pair<std::vector<int>, ll> cur;
    if (cl[P0]==0){cur=transaction(P0);cl[P0]=1;pp[P0]=cur;update(cur.fi);}
    else{
        cur=pp[P0];
    }
    ll c=0,t=0,la;
    for (int u=0;u<cur.fi.size();u++){
        if (b[cur.fi[u]]==0){
            c+=1;
            la=cur.fi[u];
        }
        t+=b[cur.fi[u]];
    }
    if(c==1){
        b[la]=P0-cur.se-t;
        for (int u=0;u<cur.fi.size();u++){
            if (b[cur.fi[u]+1]==0 && cur.fi[u]<n-1){
                query(b[cur.fi[u]]-1,n);
            }
        }
    }
    else{
        if(c>=2){
            query((P0-cur.se-t)/c,n);
            query(P0,n);
        }
        else{
            for (int u=0;u<cur.fi.size();u++){
            if (b[cur.fi[u]+1]==0 && cur.fi[u]>n-1){
                query(b[cur.fi[u]]-1,n);
            }
        }
        }
    }
}
void buy_souvenirs(int n, ll P0){
    b[0]=P0;
    int cc=0;
    k.push_back(P0-1);
    query(P0-1,n);
    for(int i=0;i<n;i++){
        while (i>a[i]){
            transaction(b[i]);
            a[i]++;
        }
    }
}

• 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