| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1254107 | garam1732 | 선물 (IOI25_souvenirs) | C++20 | 0 ms | 0 KiB |
#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;
const int MAXN = 100100*1;
const ll MOD = 1e9+7;
const ll INF = 1e9+10;
pair<vector<int>, ll> res;
int cnt[110];
ll arr[110];
std::pair<std::vector<int>, long long> transaction(long long M);
void dnc(int s, int e, ll tot) {
ll sum = tot - res.ss;
auto v = res.ff; int sz = v.size();
if(s == e) {
arr[s] = sum;
return;
}
if(sz == 1) {
arr[s] = sum;
res = transaction(sum-1);
for(int x:res.ff) cnt[x]++;
dnc(s+1, e, sum-1);
return;
}
ll avg = sum/sz;
res = transaction(avg);
for(int x:res.ff) cnt[x]++;
int idx = res.ff[0];
dnc(idx, e, avg);
while(v.size() && v.back() >= idx) {
sum -= arr[v.back()]; v.pop_back();
}
res = make_pair(v, 0);
dnc(s, idx-1, sum);
}
void buy_souvenirs(int N, ll P0) {
res = transaction(P0-1);
for(int x:res.ff) cnt[x]++;
dnc(1, N-1, P0-1);
for(int i=1; i<N; i++) {
while(cnt[i] < i) {
transaction(arr[i]);
cnt[i]++;
}
}
}
namespace {
const int CALLS_CNT_LIMIT = 10'000;
int calls_cnt;
int N;
std::vector<long long> P;
std::vector<int> Q;
void quit(const char* message) {
printf("%s\n", message);
exit(0);
}
} // namespace
std::pair<std::vector<int>, long long> transaction(long long M) {
calls_cnt++;cout<<M<<": ";
if (calls_cnt > CALLS_CNT_LIMIT)
quit("Too many calls");
if (M >= P[0] || M < P[N - 1])
quit("Invalid argument");
std::vector<int> L;
long long R = M;
for (int i = 0; i < N; i++) {
if (R >= P[i]) {
R -= P[i];
Q[i]++;
L.push_back(i);
}
}for(int x:L)cout<<x<<bl;cout<<R<<endl;
return {L, R};
}
int main() {
assert(1 == scanf("%d", &N));
P.resize(N);
for (int i = 0; i < N; i++)
assert(1 == scanf("%lld", &P[i]));
fclose(stdin);
Q.assign(N, 0);
calls_cnt = 0;
buy_souvenirs(N, P[0]);
for (int i = 0; i < N; i++)
printf("%s%d", i ? " " : "", Q[i]);
printf("\n");
fclose(stdout);
return 0;
}