Submission #1259768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259768		dattenlamj	Souvenirs (IOI25_souvenirs)	C++20	25 / 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> b){
  for(int i=0;i<b.size();i++){
    a[b[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;
  for (int i=0;i<n-1;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);
        if (cur.fi.size()==1){
            break;
        }
        P0=(P0-1-cur.se)/2;
    }
    for (int i=k.size()-1;i>=0;i--){
        ll t=0,c=0;
        for (int u=1;u<pp[i].fi.size();u++){
        if (b[pp[i].fi[u]-1]==0){
            c=1;
            break;
        }
        t+=b[pp[i].fi[u]-1];
        }
        if (c==1){
            continue;
        }
        b[pp[i].fi[0]]=k[i]-t-pp[i].se;
    }
  }
  for(int i=1;i<n;i++){
    while (a[i]<i){
        transaction(b[i]);
        a[i]++;
    }
  }
}

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