제출 #1258421

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

souvenirs

#include <iostream>
#include <vector>
#define int long long
//#define TEST 1
using namespace std;

pair<vector<int32_t>, long long> transaction(long long m);
void buy_souvenirs(int32_t n, long long p0) {
    if (n <= 3) {
        auto x = transaction(p0 - 1);
        if (n == 2) return;
        if(x.first.size() == 1) 
            transaction((p0 - 2 - x.second)),
            transaction((p0 - 2 - x.second));
        else transaction((p0 - 1 - x.second) / 2);
        return;
    }
    int p = p0, o = n - 1;
    for (int i = 1; i < n; ++i) {
        if ((i == (n - 1)) && (o != i)) {
            for (int j = 0; j < o; ++j) transaction(1);
            break;
        }
        auto x = transaction(p - 1);
        int v = p - 1;
        if ((x.second) || (x.first.size() > 1))
            --v;
        if(x.first.size() > 1) --o;
        for (int j = 1; j < i; ++j) transaction(v);
        p = v;
    }
}
#ifdef TEST
vector<int> p = {99, 97, 95, 93, 91, 89, 87, 85, 83, 81, 79, 77, 75, 73, 71, 69, 67, 65, 63, 61, 59, 57, 55, 53, 51, 49, 47, 45, 43, 41, 39, 37, 35, 33, 31, 29, 27, 25, 23, 21, 19, 17, 15, 13, 11, 9, 7, 5, 3};
pair<vector<int32_t>, long long> transaction(long long m) {
    cout << m << ": ";
    vector<int32_t> v;
    for (int i = 0; i < p.size(); ++i)
        if (p[i] <= m) {
            cout << i << " "; 
            m -= p[i];
            v.push_back(i);
        }
    cout << "rem: " << m << endl;
    return { v, m };
}
int32_t main() {
    buy_souvenirs(p.size(), p[0]);
}
#endif

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