Submission #1252491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252491		ollelap	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	428 KiB

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>

using namespace std;
#include<bits/stdc++.h>
typedef long long ll;
#define rep(i,a,b) for(int i = a; i < b; i++)

void buy_souvenirs(int N, long long P0) {
    if (N == 2) {
        pair<vector<int>, ll> res = transaction(P0-1);
        return;
    }
    if (N == 3) {
        pair<vector<int>, ll> res = transaction(P0-1);
        if (res.first.size() == 2) {
            ll remain = res.second;
            ll used = P0-1-remain;
            res = transaction(used/2);
        }
        else {
            ll A = P0-1 - res.second;
            res = transaction(A-1);
            res = transaction(A-1);
        }
        return;
    }

    int n = N;
    vector<int> q_cnt(n, 0);

    vector<int> here;
    ll sum;
    ll remainder;
    auto q = [&](ll price) {
        pair<vector<int>, ll> res = transaction(price);
        here = res.first;
        remainder = res.second;
        sum = price - remainder;
        for (auto x : here) q_cnt[x]++;
    };

    vector<int> has(n, 0);
    vector<set<int>> obj(n);
    vector<ll> s(n,0);

    vector<ll> val(n, -1);

    ll p = P0-1;
    while (!(here.size() == 1 && here[0] == N-1)) {
        q(p);
        if (here.size() == 1) p = sum-1;
        else p = sum / here.size();

        has[here[0]] = 1;
        for (auto x : here) obj[here[0]].insert(x);
        s[here[0]] = sum;
    }

    val[n-1] = s[n-1];

    auto clear = [&](int x) {
        rep(i,0,x) {
            if (obj[i].find(x) != obj[i].end()) {
                obj[i].erase(x);
                s[i] -= val[x];
            }
        }
    };

    clear(n-1);

    int un_finished = n-2;
    int iter = 0;
    while (un_finished && iter++ < 1000) {
        for (int i = n-2; i >= 0; i--) {
            if (val[i] != -1 && val[i+1] != -1) continue;

            if (val[i] == -1 && obj[i].size() == 1) {
                val[i] = s[i];
                clear(i);
                un_finished--;
                break;
            }

            if (val[i] != -1 && has[i+1] == 0) {
                q(val[i]-1);
                has[here[0]] = 1;
                for (auto x : here) obj[here[0]].insert(x);
                s[here[0]] = sum;
                for (auto x : here) if (val[x] != -1) {
                    s[here[0]] -= val[x];
                    obj[here[0]].erase(x);
                }
                break;
            }

            if (has[i] && val[i] == -1) {
                ll p = s[i] / obj[i].size();
                q(p);
                has[here[0]] = 1;
                for (auto x : here) obj[here[0]].insert(x);
                s[here[0]] = sum;
                for (auto x : here) if (val[x] != -1) {
                    s[here[0]] -= val[x];
                    obj[here[0]].erase(x);
                }
                break;
            }
        }    
    }

    rep(i,0,n) while (q_cnt[i] < i) q(val[i]);

    //rep(i,0,n) cout << val[i] << " "; cout << endl;
}



// sum(S) = a, P[-1] > b
// next query : a/size(S)?

// x + y + z = s, x > y > z
// consider Q[i] = P[i] + i, then Q[0] >= Q[1] >= ...

• 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