제출 #1251967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251967		inksamurai	선물 (IOI25_souvenirs)	C++20	25 / 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;

// pair<vi,ll> transaction(ll sum){
// 	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){
	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();

		int i=vs[0];
		if(sz(vs)==1){
			a[i]=sum;
		}else{
			self(self,sum/2);
			
			// 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;
		}

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

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

	// rep(i,n){
	// 	assert(a[i]>=0);
	// }

	rep(i,n){
		rep(_,i-cnt[i]){
			transaction(a[i]);
		}
	}
	// rep(i,n){
	// 	cout<<a[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: 0 / 14
• Subtask 4: 18 / 18
• Subtask 5: 0 / 28
• Subtask 6: 0 / 33