| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1334722 | Rares | 선물 (IOI25_souvenirs) | C++20 | 0 ms | 0 KiB |
#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=110;
int rez[MAXN],nr[MAXN];
set <int> d[MAXN];
int sum[MAXN];
void buy_souvenirs(int n, int p0){
rez[0]=p0;
for (int i=1;i<n;++i) rez[i]=-1;
while (1){
bool ok=0;
for (int i=0;i<n;++i){
if (rez[i]==-1){
ok=1;
break;
}
}
if (ok==0) break;
ok=0;
for (int i=n-1;i>=0;--i){
if (rez[i]==-1) ok=1;
if (rez[i]!=-1 and ok){
auto [v,aux]=transaction (rez[i]-1);
int x=rez[i]-1-aux;
set <int> s;
for (auto crt:v){
nr[crt]++;
if (rez[crt]!=-1){
x-=rez[crt];
}
else{
s.insert (crt);
}
}
d[i+1]=s;
sum[i+1]=x;
break;
}
if (d[i].size ()==1){
rez[i]=sum[i];
for (int j=0;j<n;++j){
if (d[j].count (i)){
sum[j]-=rez[i];
d[j].erase (i);
}
}
break;
}
if (d[i].size ()){
int x=sum[i]/d[i].size ();
auto [v,aux]=transaction (x);
x=x-aux;
set <int> s;
for (auto crt:v){
nr[crt]++;
if (rez[crt]!=-1){
x-=rez[crt];
}
else{
s.insert (crt);
}
}
int f=*s.begin ();
d[f]=s;
sum[f]=x;
break;
}
}
}
for (int i=1;i<n;++i){
while (nr[i]<i){
transaction (rez[i]);
nr[i]++;
}
}
}