Submission #1252058

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

souvenirs

#include <bits/stdc++.h>

#include "souvenirs.h"

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define fi first
#define se second
#define vec vector
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

// vec<ll> cost;

int asked=0;

// pair<vi,ll> transaction(ll sum){
// 	asked+=1;
// 	vi vs;
// 	rep(i,sz(cost)){
// 		if(sum>=cost[i]){
// 			sum-=cost[i];
// 			vs.pb(i);
// 		}
// 	}
// 	return {vs,sum};
// }

void buy_souvenirs(int N, long long P0){
	asked=0;
	int n=N;
	ll p0=P0;
	p0--;

	vec<ll> a(n,-1);
	a[0]=p0;
	vec<ll> cnt(n);
	auto rec=[&](auto self,ll p0)->void{
		auto [vs,left]=transaction(p0);
		ll sum=p0-left;

		for(auto v:vs) cnt[v]+=1;

		// print("current sum = ",sum);
		// print("indices are");
		// for(auto v:vs) cout<<v<<" ";
		// print();

		while(1){
			ll cur_sum=sum;
			int cur_neg=0;
			rep(i,sz(vs)){
				if(a[vs[i]]<0){
					// cout<<vs[i]<<" ";
					cur_neg+=1;
				}else{
					cur_sum-=a[vs[i]];
				}
			}
			// print();

			if(cur_neg==0){
				break;
			}

			// print(sz(vs),"during interation uknowns = ",cur_neg," sum = ",cur_sum);
			if(cur_neg==1){
				assert(a[vs[0]]<0);
				a[vs[0]]=cur_sum;
				break;
			}
			
			// print(sz(vs),"during interation uknowns = ",cur_neg," sum = ",cur_sum/sz(vs));
			self(self,cur_sum/cur_neg);
		}
		// int i=vs[0];
		// if(sz(vs)==1){
		// 	a[i]=sum;
		// }else{
		// 	bool need_update=0;
		// 	rng(iter,1,sz(vs)){
		// 		if(a[vs[iter]]==-1){
		// 			need_update=1;
		// 		}
		// 	}

		// 	if(need_update){
		// 		int j=vs[1];
		// 		ll new_sum=sum*0.33;
		// 		// new_sum*=sz(vs)-1;
		// 		rng(k,i+1,j) if(a[k]!=-1){
		// 			new_sum=a[k]-1;
		// 			break;
		// 		}
		// 		// if(new_sum==23) print("wtf",i,j,a[j]);
		// 		self(self,new_sum);
		// 	}
			
		// 	// rep(j,n) cout<<a[j]<<" ";
		// 	// print();

		// 	// print(i,vs[1]);
		// 	rng(iter,1,sz(vs)) assert(a[vs[iter]]!=-1);
		// 	// substract all of the others
		// 	rng(iter,1,sz(vs)) sum-=a[vs[iter]];
		// 	a[vs[0]]=sum;
		// }

		int i=vs[0];
		while(i<n and a[i]!=-1) i+=1;

		if(i<n){
			self(self,a[i-1]-1);
		}
	};
	rec(rec,p0);

	// print(n);
	// rep(i,n) cout<<cost[i]<<" ";
	// print();
	rep(i,n){
		// print(i,cnt[i]);
		assert(a[i]>=0);
		assert(cnt[i]<=i);
	}

	// rep(i,n) cout<<i-cnt[i]<<" ";
	// print();

	rep(i,n){
		while(cnt[i]<i){
			transaction(a[i]);
			cnt[i]+=1;
		}
	}

	// print(asked);
	assert(asked<=5000);
	// rep(i,n){
	// 	cout<<a[i]<<" ";
	// }
	// print();

	// rep(i,n) cout<<cnt[i]<<" ";
	// print();

	rep(i,n) assert(cnt[i]==i);
}

// int main(){
// 	int t;
// 	cin>>t;
// 	rep(cs,t){
// 		// cost={67,37,24,13,8,5};
// 		// int n=sz(cost);
// 		int n;
// 		cin>>n;
// 		cost=vec<ll>(n);
// 		rep(i,n) cin>>cost[i];
// 		buy_souvenirs(n,cost[0]);
// 		// print("~ ~ ~",cs);
// 	}
// }

• 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