Submission #1264306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264306		anango	Souvenirs (IOI25_souvenirs)	C++20	0 / 100	0 ms	420 KiB

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>
#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<int> known;
vector<int> times_bought;

void prv(vector<int> &v) {
    for (auto i:v) {
        cout << i <<" ";
    }
    cout << endl;
}

void update_times(vector<int> &bought_elements) {
    for (int i:bought_elements) {
        times_bought[i]++;
    }
}

void update_times(vector<int32_t> &bought_elements) {
    for (int i:bought_elements) {
        times_bought[i]++;
    }
}

void solve(int l, int r, int beginning_query_value, pair<vector<int32_t>, long long> res) {
    assert(l<=r);
    vector<int> bought(res.first.begin(), res.first.end());
    int num_bought = bought.size();
    int change = res.second;
    //cout << "TESTING " << l << " " << r <<" " << beginning_query_value <<" " << num_bought <<" " << change << " " << endl;
    prv(bought);
    assert(bought[0] == l);
    while (bought.size() && bought.back() > r) {
        assert(known[bought.back()]!=-1);
        change += known[bought.back()];
        bought.pop_back();
        num_bought--;
    }
    assert(bought.size()>0);
    if (num_bought==1) {
        int known_value_l = beginning_query_value - change;
        assert(known[l] == -1 || known[l] == known_value_l);
        known[l] = known_value_l;
        if (l==r) {
            return;
        }
    }
    assert(l<r);
    int total = beginning_query_value - change;
    int average = total / num_bought;
    pair<vector<int32_t>, long long> next_res = transaction(average);
    vector<int> next_bought(next_res.first.begin(), next_res.first.end());
    update_times(next_bought);
    int new_left = next_res.first[0];
    assert(new_left > l && new_left <= r);
    solve(new_left, r, average, next_res);
    solve(l, new_left-1, beginning_query_value, res);

}

void buy_souvenirs(int32_t N, long long P0) {
    //let's say that you start by doing P[0]-1
    //this guarantees that you buy the first souvenir
    //then you can repeat the same process with the rest of the souvenirs
    //ok so our method is
    //start with P[0]-1
    //then let S be the set of bought souvenirs
    //take the average of S (it's known from the given info)
    //transaction based on this
    //then say the first souvenir bought is i, it means that from 1 to i-1 the souvenirs are more than S
    //and from i to N-1 the souvenirs are less than S
    //solve i to N-1 recursively with the same process
    //and then solve 1 to i-1 also recursively using the info from i to N-1
    //and then once we know all the values we can do the required transactions with full information
    //we need to implement a function that will solve from l to r, knowing all values past r
    //and then do a recursive search, which takes in a value known to be smaller than the l-1th, and larger or equal than the lth (this is how l is chosen)
    //and fills in the known values for this range
    //updating the times bought for each value in between
    //the query limit is safe since at least one souvenir is bought on each purchase
    known=vector<int>(N, -1);
    times_bought=vector<int>(N, 0);
    pair<vector<int32_t>, long long> first_transaction = transaction(P0-1);
    vector<int> first_bought(first_transaction.first.begin(), first_transaction.first.end());
    solve(1, N-1, P0-1, first_transaction);
    update_times(first_bought);
    for (int i=1; i<N; i++) {
        //cout << i <<" " << known[i] << " " << times_bought[i] << endl;
        assert(known[i]!=-1);
        assert(times_bought[i]<=i);
        while (times_bought[i]<i) {
            pair<vector<int32_t>, long long> useless_transaction = transaction(known[i]);
            update_times(useless_transaction.first);
        }
    }
    return;
}

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