제출 #1249843

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

souvenirs

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

const int N = 104;

vector<int> vec,v[N];
ll sum[N];
ll res;
int n,freq[N];
ll p[N];

void my_transaction(ll m){
    auto x = transaction(m);
    vec = x.first;
    res = x.second;
}

void completar(int i){
    while (freq[i] < i){
        transaction(p[i]);
        freq[i]++;
    }
}

ll min_val(ll S,int k){
    int val = k*(k-1)/2;
    S +=  val + k-1;
    return S/k;
}

void go(ll limit){
    // cout << "go : " << limit << "\n";
    my_transaction(limit);
    int pos = *vec.begin();
    sum[pos] = limit - res;
    v[pos] = vec;

    for (int x : vec)
        freq[x]++;

    while (v[pos].size() > 1){
        while (p[v[pos].back()] > 0){
            sum[pos] -= p[v[pos].back()];
            v[pos].pop_back();
        }
        int k = v[pos].size();
        if (k > 1)
            go(min_val(sum[pos], k) - 1);
    }
    // cout << "sale while " << limit << " -> " << sum[pos] << "\n";
    p[pos] = sum[pos];
    if (pos+1 < n && p[pos+1] == 0)
        go(p[pos] - 1);
    // cout << "sale " << limit << "\n";
}

void buy_souvenirs(int N,ll p0){
    n = N;
    p[0] = p0;
    go(p0 - 1);
/*
    cout << "p : ";
    for (int i=0; i<n; i++)
        cout << p[i] << " ";
    cout << "\n";
*/
    for (int i=1; i<n; i++)
        completar(i);
}

• 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