Submission #1259830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259830		dattenlamj	Souvenirs (IOI25_souvenirs)	C++20	39 / 100	12 ms	788 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];
std::vector<std::pair<std::vector<int> , ll > > pp;
std::vector <ll> k;
void buy_souvenirs(int n, ll P0){
  b[0]=P0;
  int cc=0;
  while (cc<n-1){
  for (int i=n-2;i>=0;i--){
    if(b[i]==0 || b[i+1]!=0){
        continue;
    }
    P0=b[i]-1;
    while (true){
        std::pair<std::vector<int>, ll> cur = transaction(P0);
        update(cur.fi);
        pp.push_back(cur);
        k.push_back(P0);
        ll c=0;
        for (int u=0;u<cur.fi.size();u++){
            if (b[cur.fi[u]]==0){
                c+=1;
            }
        }
        if (c==1){
            break;
        }
        P0=(P0-cur.se)/cur.fi.size();
    }
    for (int yyyyy=0;yyyyy<k.size();yyyyy++){
    for (int lll=k.size()-1;lll>=0;lll--){
        ll t=0,c=0,la;
        for (int u=0;u<pp[lll].fi.size();u++){
        if (b[pp[lll].fi[u]]==0){
            c+=1;
            la=pp[lll].fi[u];
        }
        t+=b[pp[lll].fi[u]];
        }
        if (c==1){
            b[la]=k[lll]-t-pp[lll].se;
            cc++;
        }
    }
    }
    break;
  }
  }
  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: 0 / 28
• Subtask 6: 0 / 33