Submission #1251122

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

souvenirs

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define inf 1ll<<60
#define rep(i,a,b) for (ll i=a;i<(b);i++)
#define MP make_pair
#define mod (ll)998244353
#define SZ(x) (int(x.size()))
#define ALL(x) x.begin(),x.end()
#define endl "\n"
ll lowbit(ll x) {return x&(-x);}

#include "souvenirs.h"
struct eqn{
	vector<int>elem; ll sum;
	eqn(vector<int>e, ll s): elem(e), sum(s){}
	void clear(vector<ll>&P, ll bound){
		while(elem.back()>bound){
			sum-=P[elem.back()];
			elem.pop_back();
		}
	}
};

eqn modified_transaction(ll m){
	pair<vector<int>,ll> tmp = transaction(m);
	return {tmp.fi,m-tmp.se}; //sum of all items brought
}

void buy_souvenirs(int N, long long P0) {
	vector<ll>P(N,0),rem(N,0);
	rep(i,1,N)rem[i]=i;
	stack<eqn>s; //store the states
	ll bound = N-1; //found P[i] for all i>bound
	s.push({{0},P0});
	while(bound){
		eqn u=s.top();
		u.clear(P,bound); //remove all confirmed P[i] from eqn
		if(u.elem.size()==1 and u.elem[0]==bound){ //found a new P[bound]
			s.pop();
			P[bound]=u.sum;
			bound--;
		}else{
			ll amt = (u.sum-1)/u.elem.size(); //only items with P < P max in the set could be brought
			eqn next = modified_transaction(amt); //thus will repeat until we get P[bound]
			for(auto x:next.elem)rem[x]--;
			s.push(next);
		}
	}
	rep(i,1,N)while(rem[i]--)transaction(P[i]);
	return;
}
//max number of purchases is 4950 so 5000 is useless info

• 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