Submission #1252021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252021		PoonYaPat	Souvenirs (IOI25_souvenirs)	C++20	0 / 100	0 ms	420 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<vector<int>,ll> pvl;

ll n,val[105],cnt[105];

// find all the items that has value at most s by buying the most expensive item that less than s (v[0]) only once
void solve(ll s) {
  pvl res=transaction(s);
  s-=res.second;
  vector<int> v=res.first;
  for (auto s : v) ++cnt[s];

  while (1) {
    for (int i=(int)(v.size()-1); i>=0; --i) {
      if (val[v[i]]!=-1) s-=val[v[i]], v.pop_back();
      else if (i) {
        solve(s/((int)(v.size())));
        break;
      } else {
        val[v[0]]=s;
        cout<<v[0]<<" "<<s<<"\n";
        if (v[0]!=n-1) solve(val[v[0]]-1);
        return;
      }
    }
    if (v.size()==0) break;
  }

}

void buy_souvenirs(int N, ll P0) {
  n=N;
  memset(val,-1,sizeof(val));
  solve(P0-1);
  for (int i=0; i<n; ++i) {
    for (int j=0; j<i-cnt[i]; ++j) transaction(val[i]);
  }
}

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