제출 #1250597

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

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

void buy_souvenirs(int N, ll P0) {
    if (N == 2) {
        // subtask 1
        auto res = transaction(P0 - 1);
    } else if (N == 3) {
        // subtask 4
        ll x = P0 - 1;
        auto res = transaction(x);
        if (res.first.size() == 1) {
            ll rem = res.second;
            ll y = x - rem;
            ll z = y - 1;

            res = transaction(z);
            res = transaction(z);
        } else if (res.first.size() == 2) {
            ll rem = res.second;
            ll b = x - rem;
            ll m = (b+1) / 2;
            ll z = m - 1;
            res = transaction(z);
        } else assert(0);
    } else {
        // subtask 2
        // for (int i = 0; i < N; i++) {
        //     for (int j = 0; j < i; j++) {
        //         auto res = transaction(N - i);
        //     }
        // }

        // subtask 3
        vector<ll> vals(N, -1);
        vals[0] = P0;
        vector<int> cnt(N);
        for (int i = 1; i < N; i++) {
            if (cnt[i] == i) continue;
            if (vals[i] != -1) {
                while (cnt[i] < i) {
                    auto res = transaction(vals[i]);
                    cnt[i]++;
                }
                continue;
            }
            assert(vals[i-1] != -1);
            auto res = transaction(vals[i-1] - 1);
            auto v = res.first;
            ll rem = res.second;
            if (v.empty()) continue;
            else if (v[0] == i and v.size() == 1 and rem == 0) {
                cnt[i]++;
                vals[i] = vals[i-1] - 1;

                while (cnt[i] < i) {
                    res = transaction(vals[i]);
                    cnt[i]++;
                }
            } else {
                for (auto &x : v) cnt[x]++;
                assert(v[0] == i);
                if (v.size() == 2) assert(rem == 0), vals[v[1]] = 1;

                vals[i] = vals[i-1] - 2;

                while (cnt[i] < i) {
                    res = transaction(vals[i]);
                    cnt[i]++;
                }
            }
        }
    }
    // pair<vector<int>, long long> res = transaction(3);
    return;
}

• 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