# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
522270 |
2022-02-04T11:53:37 Z |
vonatlus |
Gift (IZhO18_nicegift) |
C++17 |
|
381 ms |
37660 KB |
/// adil sultanov | vonat1us
#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:36777216")
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define sz(x) (int) x.size()
#define all(z) (z).begin(), (z).end()
using namespace std;
using ll = long long;
using pii = pair<ll, int>;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 1e2;
void fin() {
#ifdef AM
freopen(".in", "r", stdin);
#endif
}
const bool flag = 0;
const int N = 1e6+10;
pii t[N<<2];
ll a[N], n;
void build(int u = 0, int l = 0, int r = n) {
if (r-l == 1) {
t[u] = {a[l], l};
return;
}
int m = l+r >> 1;
build(u+u+1, l, m);
build(u+u+2, m, r);
t[u] = max(t[u+u+1], t[u+u+2]);
}
void modify(int pos, ll val, int u = 0, int l = 0, int r = n) {
if (r-l == 1) {
t[u].x = val;
return;
}
int m = l+r >> 1;
if (pos < m) {
modify(pos, val, u+u+1, l, m);
} else {
modify(pos, val, u+u+2, m, r);
}
t[u] = max(t[u+u+1], t[u+u+2]);
}
void ma1n() {
ll k;
cin >> n >> k;
ll sum = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i], sum += a[i];
}
if (sum%k) {
cout << -1, exit(0);
}
if (*min_element(a, a+n) == *max_element(a, a+n)) {
cout << n << "\n";
for (int i = 0; i < n; ++i) {
cout << a[i]/k << " ";
for (int j = i; j < i+k; ++j) {
cout << (j%n)+1 << " ";
}
cout << "\n";
}
return;
}
vector<int> ans;
build();
while (1) {
if (t[0].x == 0) break;
vector<pii> v;
for (int i = 0; i < k; ++i) {
if (t[0].x == 0) {
cout << -1, exit(0);
}
v.pb({t[0].y, t[0].x});
modify(t[0].y, 0);
}
ll d = v.back().y-(t[0].x ? t[0].x : 1)+1;
ans.pb(d);
for (pii& x : v) {
ans.pb(x.x+1);
modify(x.x, x.y-d);
}
}
cout << sz(ans)/(k+1) << "\n";
for (int i = 0; i < sz(ans); i += k+1) {
for (int j = i; j <= i+k; ++j) {
cout << ans[j] << " ";
}
cout << "\n";
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr), fin();
int ts = 1;
if (flag) {
cin >> ts;
}
while (ts--) {
ma1n();
}
return 0;
}
Compilation message
nicegift.cpp: In function 'void build(int, int, int)':
nicegift.cpp:41:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
41 | int m = l+r >> 1;
| ~^~
nicegift.cpp: In function 'void modify(int, ll, int, int, int)':
nicegift.cpp:52:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | int m = l+r >> 1;
| ~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
n=4 |
2 |
Correct |
1 ms |
204 KB |
n=3 |
3 |
Correct |
0 ms |
204 KB |
n=3 |
4 |
Correct |
0 ms |
204 KB |
n=4 |
5 |
Correct |
1 ms |
204 KB |
n=4 |
6 |
Correct |
0 ms |
204 KB |
n=2 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
n=4 |
2 |
Correct |
1 ms |
204 KB |
n=3 |
3 |
Correct |
0 ms |
204 KB |
n=3 |
4 |
Correct |
0 ms |
204 KB |
n=4 |
5 |
Correct |
1 ms |
204 KB |
n=4 |
6 |
Correct |
0 ms |
204 KB |
n=2 |
7 |
Correct |
1 ms |
332 KB |
n=5 |
8 |
Correct |
1 ms |
332 KB |
n=8 |
9 |
Correct |
3 ms |
588 KB |
n=14 |
10 |
Correct |
2 ms |
460 KB |
n=11 |
11 |
Correct |
27 ms |
3624 KB |
n=50000 |
12 |
Correct |
33 ms |
3936 KB |
n=50000 |
13 |
Correct |
10 ms |
976 KB |
n=10 |
14 |
Correct |
30 ms |
1356 KB |
n=685 |
15 |
Correct |
27 ms |
1536 KB |
n=623 |
16 |
Correct |
16 ms |
976 KB |
n=973 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
n=4 |
2 |
Correct |
1 ms |
204 KB |
n=3 |
3 |
Correct |
0 ms |
204 KB |
n=3 |
4 |
Correct |
0 ms |
204 KB |
n=4 |
5 |
Correct |
1 ms |
204 KB |
n=4 |
6 |
Correct |
0 ms |
204 KB |
n=2 |
7 |
Correct |
1 ms |
332 KB |
n=5 |
8 |
Correct |
1 ms |
332 KB |
n=8 |
9 |
Correct |
3 ms |
588 KB |
n=14 |
10 |
Correct |
2 ms |
460 KB |
n=11 |
11 |
Correct |
27 ms |
3624 KB |
n=50000 |
12 |
Correct |
33 ms |
3936 KB |
n=50000 |
13 |
Correct |
10 ms |
976 KB |
n=10 |
14 |
Correct |
30 ms |
1356 KB |
n=685 |
15 |
Correct |
27 ms |
1536 KB |
n=623 |
16 |
Correct |
16 ms |
976 KB |
n=973 |
17 |
Correct |
31 ms |
1456 KB |
n=989 |
18 |
Correct |
21 ms |
924 KB |
n=563 |
19 |
Correct |
28 ms |
1208 KB |
n=592 |
20 |
Correct |
26 ms |
1236 KB |
n=938 |
21 |
Correct |
17 ms |
976 KB |
n=747 |
22 |
Correct |
21 ms |
1120 KB |
n=991 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
381 ms |
35972 KB |
n=1000000 |
2 |
Incorrect |
287 ms |
37660 KB |
Not all heaps are empty in the end |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
n=4 |
2 |
Correct |
1 ms |
204 KB |
n=3 |
3 |
Correct |
0 ms |
204 KB |
n=3 |
4 |
Correct |
0 ms |
204 KB |
n=4 |
5 |
Correct |
1 ms |
204 KB |
n=4 |
6 |
Correct |
0 ms |
204 KB |
n=2 |
7 |
Correct |
1 ms |
332 KB |
n=5 |
8 |
Correct |
1 ms |
332 KB |
n=8 |
9 |
Correct |
3 ms |
588 KB |
n=14 |
10 |
Correct |
2 ms |
460 KB |
n=11 |
11 |
Correct |
27 ms |
3624 KB |
n=50000 |
12 |
Correct |
33 ms |
3936 KB |
n=50000 |
13 |
Correct |
10 ms |
976 KB |
n=10 |
14 |
Correct |
30 ms |
1356 KB |
n=685 |
15 |
Correct |
27 ms |
1536 KB |
n=623 |
16 |
Correct |
16 ms |
976 KB |
n=973 |
17 |
Correct |
31 ms |
1456 KB |
n=989 |
18 |
Correct |
21 ms |
924 KB |
n=563 |
19 |
Correct |
28 ms |
1208 KB |
n=592 |
20 |
Correct |
26 ms |
1236 KB |
n=938 |
21 |
Correct |
17 ms |
976 KB |
n=747 |
22 |
Correct |
21 ms |
1120 KB |
n=991 |
23 |
Correct |
381 ms |
35972 KB |
n=1000000 |
24 |
Incorrect |
287 ms |
37660 KB |
Not all heaps are empty in the end |
25 |
Halted |
0 ms |
0 KB |
- |