Submission #1289488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289488		edo	선물 (IOI25_souvenirs)	C++20	35 / 100	12 ms	400 KiB

souvenirs

#include <bits/stdc++.h>

using namespace std;
using ll   = long long;
using vi   = vector<int>;
using vll  = vector<ll>;
using vvi  = vector<vi>;
using vvll = vector<vll>;
using pii  = pair<int,int>;
using pll  = pair<ll,ll>;
using ui    = unsigned int;
using ull   = unsigned long long;
using pui   = pair<ui,ui>;
using pull  = pair<ull,ull>;

template<typename T>
using vc = std::vector<T>;


#define YES cout << "YES\n"
#define NO  cout << "NO\n"
#define yes cout << "yes\n"
#define no  cout << "no\n"
#define Yes cout << "Yes\n"
#define No  cout << "No\n"

template<typename T> void sc(T &x) { cin >> x; }
template<typename T, typename U> void sc(pair<T,U> &p) { sc(p.fi), sc(p.se); }
template<typename T> void sc(vector<T> &v) { for (auto &x : v) sc(x); }
template<typename... A> void sc(A&... a) { (sc(a), ...); }


template<typename T> void _pt(const T &x){cout << x;}
template<typename T, typename U> void _pt(const pair<T,U> &p){_pt(p.fi); cout << ' '; _pt(p.se);}
template<typename T> void _pt(const vector<T> &v){bool f=1; for(auto &x:v){if(!f) cout<<' '; _pt(x); f=0;}}
template<typename... A> void pt(const A&... a){(_pt(a), ...);}


template<typename T, typename U> bool umin(T &a, const U &b) { return b < a ? (a = b, true) : false; }
template<typename T, typename U> bool umax(T &a, const U &b) { return b > a ? (a = b, true) : false; }
template<typename T> T maxel(const vector<T>& v){ return *max_element(v.begin(), v.end()); }
template<typename T> T minel(const vector<T>& v){ return *min_element(v.begin(), v.end()); }
template<typename T> int lb(const vector<T>& v, const T& x){ return lower_bound(v.begin(), v.end(), x) - v.begin(); }
template<typename T> int ub(const vector<T>& v, const T& x){ return upper_bound(v.begin(), v.end(), x) - v.begin(); }
template<typename T> auto lbid(vector<T>& v, const T& x){ return lower_bound(v.begin(), v.end(), x); }
template<typename T> auto ubid(vector<T>& v, const T& x){ return upper_bound(v.begin(), v.end(), x); }

#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define FOR1(n)            for (int i=0; i<(n); ++i)
#define FOR2(i,n)          for (int i=0; i<(n); ++i)
#define FOR3(i,l,r)        for (int i=(l); i<(r); ++i)
#define FOR4(i,l,r,k)      for (int i=(l); i<(r); i+=(k))
#define FOR(...)           GET_MACRO(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define ROF1(n)            for (int i=(n)-1; i>=0; --i)
#define ROF2(i,n)          for (int i=(n)-1; i>=0; --i)
#define ROF3(i,l,r)        for (int i=(r)-1; i>=(l); --i)
#define ROF4(i,l,r,k)      for (int i=(r)-1; i>=(l); i-=(k))
#define ROF(...)           GET_MACRO(__VA_ARGS__, ROF4, ROF3, ROF2, ROF1)(__VA_ARGS__)
#define all(c)   (c).begin(), (c).end()
#define allr(c)  (c).rbegin(), (c).rend()
#define eb       emplace_back
#define mp       make_pair
#define mt       make_tuple
#define fi       first
#define se       second
#define pb       push_back
#define trav(x,a) for (auto &x : (a))
#define sz(a) ((int)(a).size())
#define mem(a,v) memset(a, v, sizeof(a))
#define nl pt("\n")

#if defined(LOCAL) && __has_include("../../debug.h")
  #include "../../debug.h"
#elif defined(LOCAL) && __has_include("../debug.h")
  #include "../debug.h"
#elif defined(LOCAL) && __has_include("debug.h")
  #include "debug.h"
#else
  #define debug(...) ((void)0)
#endif

namespace std {
 
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));
}
 
} // namespace std

#include "souvenirs.h"

pair<vi, ll> ask(ll x) {
    return transaction(x);
}

ll ask2(ll x, int y) {
    return ((x * 2) / y + 1 - y) / 2;
}

void buy_souvenirs(int N, ll P0) {
    // p0 > p1 > p2 > 0
    // samo otkriti svaku cijenu?
    int n = N;
    if(n == 2) {
        pair<vi, ll> res = transaction(P0 - 1);
        return;
    }
    else if(n == 3) {
        pair<vi, ll> res = transaction(P0 - 1);
        // debug(res);
        ll Ask = P0 - 1 - res.se - 1;
        res = transaction(Ask);
        // debug(res);
        res = transaction(Ask);
        // debug(res);
        return;
    }
    // else if(n == 4) {
        
    // }
    vi cnt(105);
    vll val(105, -1);
    deque<int> q[105];
    vll cijena(105, -1);

    val[0] = P0;

    auto clear = [&]() {
        FOR(n) {
            if(!q[i].empty() && q[i].back() == n - 1) {
                q[i].pop_back();
                cijena[i] -= val[n - 1];
            }
        }
        --n;
    };

    y_combinator([&](auto self, int x) -> void {
        if(x == n - 1) return;
        auto res = ask(val[x] - 1);
        vi kup = res.fi;
        ll ost = res.se;
        int nx = x + 1;
        debug(kup, ost, nx);
        trav(t, kup) cnt[t]++;
        cijena[nx] = val[nx - 1] - 1 - ost;
        trav(t, kup) { 
            if(val[t] == -1) q[nx].pb(t);
            else cijena[nx] -= val[t];
        }

        while(nx < n) {
            int lst = nx;
            FOR(i, nx, n) {
                if(!q[i].empty() && val[lst] == -1) lst = i;
            }            
            if(sz(q[lst]) == 1) {
                int idx = q[lst].front();
                val[idx] = cijena[lst];
                debug(idx);
                self(idx);
                clear();
                continue;
            }

            ll p = ask2(cijena[lst], sz(q[lst]));
            auto res2 = ask(p);
            vi kup2 = res2.fi;
            ll ost2 = res2.se;

            debug(kup2, ost2, p);
            
            int y = kup2[0];
            cijena[y] = p - ost2;
            
            trav(t, kup2) ++cnt[t];
            trav(t, kup2) {
                if(val[t] == -1) q[y].pb(t);
                else cijena[y] -= val[t];
            }           
            debug(cijena);
        }
    })(0);
    
    FOR(N) {
        while(cnt[i] < i) {
            ask(val[i]);
            cnt[i]++;
        }
    }
    // pair<vi, ll> res = transaction(3);
}

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