제출 #1251263

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251263		arneves	선물 (IOI25_souvenirs)	C++20	100 / 100	12 ms	428 KiB

souvenirs

/*
           ______  _____  _______ _     _ _______ __   _  _____  _  _  _
          |_____/ |     | |       |____/  |______ | \  | |     | |  |  |
          |    \_ |_____| |_____  |    \_ ______| |  \_| |_____| |__|__|
 
 
                   .      .           .      .           .      .
                   _\/  \/_           _\/  \/_           _\/  \/_
                    _\/\/_             _\/\/_             _\/\/_
                _\_\_\/\/_/_/_     _\_\_\/\/_/_/_     _\_\_\/\/_/_/_
                 / /_/\/\_\ \       / /_/\/\_\ \       / /_/\/\_\ \
                    _/\/\_             _/\/\_             _/\/\_
                    /\  /\             /\  /\             /\  /\
                   '      '           '      '           '      '
 
*/
 
//#pragma GCC optimize("Ofast", "unroll-loops")
 
#include "bits/stdc++.h"
 
//#pragma GCC target("avx2")
//#pragma GCC target("lzcnt,popcnt")
 
using namespace std;
using ll = long long;
using bint = __int128;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
#define ff first
#define ss second
#define rep(i, a, b) for (int i=a; i<(b); ++i)
#define rev(i, a, b) for (int i=b-1; i>=(a); --i)
 
template <class Fun>
class y_combinator_result {
	Fun fun_;
 
  public:
	template <class T>
	explicit y_combinator_result(T&& fun)
		: fun_(std::forward<T>(fun)) {
	}
 
	template <class... Args>
	decltype(auto) operator()(Args&&... args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};
 
template <class Fun>
decltype(auto) y_combinator(Fun&& fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
 
string yon(ll ans) {
	return ans ? "Yes" : "No";
}
 
template <typename T>
inline void ckmin(T& a, const T b) {
	if (a > b)
		a = b;
}
 
template <typename T>
inline void ckmax(T& a, const T b) {
	if (a < b)
		a = b;
}
 
inline double get_time() {
	return std::chrono::duration_cast<std::chrono::milliseconds>(
		   std::chrono::system_clock::now().time_since_epoch())
		   .count();
}
 
ll popcnt(ll x){return __builtin_popcountll(x);}
ll popcnt_sgn(ll x){return (__builtin_parityll(x)&1 ? -1:1);}
ll topbit(ll x){return (x==0 ? -1:63-__builtin_clzll(x));}
ll lowbit(ll x){return (x==0 ? -1:__builtin_ctzll(x));}

#include "souvenirs.h"

void buy_souvenirs(int n, ll p0) {
	
	vector<int> c(n);
	vector<pair<set<int>, ll>> precos(n);
	int t=n-1;
	vector<int> done(n);
	
	rep(i,0,n) precos[i].ss=-1;
	
	precos[0]={{0}, p0};
	done[0]=1;
	
	auto query=[&](ll p) -> auto{
		//cout<<">>>"<<p<<endl;
		auto q=transaction(p);
		for(int u: q.ff) c[u]++;
		pair<set<int>, ll> ans={{all(q.ff)}, p-q.ss};
		return ans;
	};
	
	auto prop=y_combinator([&](auto self, int idx) -> void{
		if(done[idx]==0){
			done[idx]=1;
			t--;
		}
		
		rep(i,0,n) if(i!=idx && precos[i].ff.count(idx)){
			precos[i].ff.erase(idx);
			precos[i].ss-=precos[idx].ss;
			if(sz(precos[i].ff)==1) self(i);
		}
	});
	
	auto cascade=[&](ll cur) -> void{
		while(1){
			auto q=query(cur);
			int y=*q.ff.begin();
			precos[y]=q;
			
			if(done[y]) break;
			
			vector<int> rem;
			
			for(int u: precos[y].ff){
				if(done[u] && u!=y){
					precos[y].ss-=precos[u].ss;
					rem.pb(u);
				}
			}
			
			for(int u: rem) precos[y].ff.erase(u);
			
			if(sz(precos[y].ff)==1){
				prop(y);
				break;
			}else{
				cur=q.ss/sz(precos[y].ff);
			}
		}
	};
	
	while(t>0){
		//cout<<t<<'\n';
		rev(i,1,n){
			if(precos[i].ss==-1 && done[i-1]){
				cascade(precos[i-1].ss-1);
				break;
			}
			
			if(sz(precos[i].ff)>1){
				cascade(precos[i].ss/sz(precos[i].ff));
				break;
			}
		}
	}
	
	rep(i,0,n){
		while(c[i]<i){
			query(precos[i].ss);
		}
	}
	
	return;
}

• 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