Submission #1252402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252402		anfi	선물 (IOI25_souvenirs)	C++20	0 / 100	0 ms	412 KiB

souvenirs

#include"souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const long long inf = 1e9;
long long n,p[105],cn[105];
long long hitung(int s, int k){
    s += k*(k-1)/2+k-1;
    return s/k;
}

void find(int p0){
    int ls = n;
    long long money = p0-1;
    while(ls > 0){
        while(1){
            auto [v, rm] = transaction(money);
            long long sum = money-rm;
            for(int i : v) cn[i]++;
            while(!v.empty() && v.back() >= ls){
                sum -= p[v.back()]; v.pop_back();
            }
            if(v.empty()){
                money--; continue;
            }
            long long i = v[0];
            if(v.size() == 1|| i+1 == ls){
                p[i] = sum;
                ls = i;
                money = p[i]-1;
            }
            else{
                int k = v.size();
                money = hitung(sum, k)-1;
            }
        }
    }
}

void buy_souvenirs(int N, long long p0){ 
    memset(cn, 0, sizeof(cn));
    memset(p, 0, sizeof(p));
    p[0] = p0, n = N;
    find(p0);
    for(int i = 1; i < N; i++){
        while(cn[i] < i){
            transaction(p[i]);
            cn[i]++;
        }
    }
}

• 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