#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ll long long
#define int ll
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define VAR(v, i) __typeof( i) v=(i)
#define forit(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
using namespace std;
const int maxn = (int)1e6 + 10;
const int mod = (int)1e9 + 7;
const int P = (int) 1e6 + 7;
const double pi = acos(-1.0);
#define inf mod
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> Vll;
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;
typedef array<int, 3> triple;
int n, k, sum, mx;
pii a[maxn];
set<pii, greater<pii>> s;
inline void solve(){
scanf("%lld%lld", &n, &k);
forn(i, 1, n) {
scanf("%lld", &a[i].f);
a[i].s = i;
sum += a[i].f;
mx = max(mx, a[i].f);
s.insert(a[i]);
}
vector<pair<int, vi> > path;
while(1){
if(!a[1].f) break;
set<pii, greater<pii>> now = s;
int l = 1, r, res = -1;
forn(i, 1, k) r = now.begin() -> f, now.erase(now.begin());
int kth;
if(sz(now)) kth = now.begin() -> f;
else kth = 0;
int f = s.begin() -> f;
if(!f) break;
while(l <= r){
int mid = (l + r) >> 1;
int curS = sum - mid * mid, mx = max(kth, f - mid);
if(curS / k >= mx){
res = mid;
l = mid + 1;
}else
r = mid - 1;
}
assert(res != -1);
vi cur;
vpii toAdd;
forn(iter, 1, k){
cur.pb(s.begin() -> s);
toAdd.pb(*s.begin());
s.erase(s.begin());
}
for(auto x : toAdd)
s.insert({x.f - res, x.s});
sum -= res * k;
path.pb({res, cur});
}
printf("%lld\n", sz(path));
for(auto x : path){
printf("%lld ", x.f);
for(auto it : x.s) printf("%lld ", it);
puts("");
}
}
main () {
int t = 1;
//scanf("%d", &t);
while(t--)
solve();
}
Compilation message
nicegift.cpp:93:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
93 | main () {
| ^
nicegift.cpp: In function 'void solve()':
nicegift.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
40 | scanf("%lld%lld", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
nicegift.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
42 | scanf("%lld", &a[i].f);
| ~~~~~^~~~~~~~~~~~~~~~~
nicegift.cpp:62:20: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
62 | int mid = (l + r) >> 1;
| ~~~^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
n=4 |
| 2 |
Correct |
1 ms |
364 KB |
n=3 |
| 3 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
n=4 |
| 2 |
Correct |
1 ms |
364 KB |
n=3 |
| 3 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
n=4 |
| 2 |
Correct |
1 ms |
364 KB |
n=3 |
| 3 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2091 ms |
141292 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
n=4 |
| 2 |
Correct |
1 ms |
364 KB |
n=3 |
| 3 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
