# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
496326 |
2021-12-21T05:47:20 Z |
Ierus |
Gift (IZhO18_nicegift) |
C++17 |
|
606 ms |
133240 KB |
#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
using namespace std;
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
#define F first
#define S second
#define int long long
#define sz(x) (int)x.size()
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
const int E = 1e6+777;
const long long inf = 1e18+777;
const int N = 1e5+777;
const int MOD = 1e9+7;
int n, k, a[E], sum;
vector<vector<int>> res;
priority_queue<pair<int,int>> pq;
signed main(){auto solve=[&](){
cin >> n >> k;
for(int i = 1; i <= n; ++i){
cin >> a[i];
sum += a[i];
if(a[i] > 0){
pq.push({a[i], i});
}
}
bool ok = (sum % k == 0);
for(int i = 1; i <= n; ++i){
if(a[i] > sum / k) ok = false;
}
if(!ok){
cout << -1;
return;
}
int len = sum / k;
vector<vector<pair<int,int>>> m(k);
vector<int> sm(k, 0), u(k, 0);
for(int i = 1, e = 0; i <= n;){
if(sm[e] + a[i] <= len){
m[e].pb({a[i], i});
sm[e] += a[i];
++i;
}else{
int cur = len - sm[e];
if(!cur){
++e;
continue;
}
sm[e] += cur;
m[e].pb({cur, i});
a[i] -= cur;
++e;
}
if(!a[i])++i;
}
// cerr << "M\n";
// for(int i = 0; i < k; ++i){
// for(int j = 0; j < sz(m[i]); ++j){
// cerr << m[i][j].F << ' ';
// }
// cerr << '\n';
// }cerr << '\n';
auto check = [&](){
bool ok = 0;
for(int i = 0; i < k; ++i){
if(sm[i])ok=1;
}
return ok;
};
while(check()){
// cerr << "OK\n";
vector<int> r;
int mn = LLONG_MAX;
for(int i = 0; i < k; ++i){
mn = min(mn, m[i][u[i]].F);
}
r.pb(mn);
for(int i = 0; i < k; ++i){
sm[i] -= mn;
m[i][u[i]].F -= mn;
r.pb(m[i][u[i]].S);
if(m[i][u[i]].F == 0){
++u[i];
}
}
res.pb(r);
}
cout << sz(res) << '\n';
for(auto v : res){
for(auto it : v)
cout << it << ' ';
cout << '\n';
}
};NFS;solve();}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
316 KB |
n=4 |
2 |
Correct |
1 ms |
204 KB |
n=3 |
3 |
Correct |
0 ms |
204 KB |
n=3 |
4 |
Correct |
1 ms |
320 KB |
n=4 |
5 |
Correct |
1 ms |
320 KB |
n=4 |
6 |
Correct |
0 ms |
204 KB |
n=2 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
316 KB |
n=4 |
2 |
Correct |
1 ms |
204 KB |
n=3 |
3 |
Correct |
0 ms |
204 KB |
n=3 |
4 |
Correct |
1 ms |
320 KB |
n=4 |
5 |
Correct |
1 ms |
320 KB |
n=4 |
6 |
Correct |
0 ms |
204 KB |
n=2 |
7 |
Correct |
1 ms |
204 KB |
n=5 |
8 |
Correct |
1 ms |
204 KB |
n=8 |
9 |
Correct |
16 ms |
320 KB |
n=14 |
10 |
Correct |
1 ms |
204 KB |
n=11 |
11 |
Correct |
35 ms |
5308 KB |
n=50000 |
12 |
Correct |
24 ms |
5096 KB |
n=50000 |
13 |
Correct |
0 ms |
204 KB |
n=10 |
14 |
Correct |
1 ms |
332 KB |
n=685 |
15 |
Correct |
1 ms |
324 KB |
n=623 |
16 |
Correct |
1 ms |
332 KB |
n=973 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
316 KB |
n=4 |
2 |
Correct |
1 ms |
204 KB |
n=3 |
3 |
Correct |
0 ms |
204 KB |
n=3 |
4 |
Correct |
1 ms |
320 KB |
n=4 |
5 |
Correct |
1 ms |
320 KB |
n=4 |
6 |
Correct |
0 ms |
204 KB |
n=2 |
7 |
Correct |
1 ms |
204 KB |
n=5 |
8 |
Correct |
1 ms |
204 KB |
n=8 |
9 |
Correct |
16 ms |
320 KB |
n=14 |
10 |
Correct |
1 ms |
204 KB |
n=11 |
11 |
Correct |
35 ms |
5308 KB |
n=50000 |
12 |
Correct |
24 ms |
5096 KB |
n=50000 |
13 |
Correct |
0 ms |
204 KB |
n=10 |
14 |
Correct |
1 ms |
332 KB |
n=685 |
15 |
Correct |
1 ms |
324 KB |
n=623 |
16 |
Correct |
1 ms |
332 KB |
n=973 |
17 |
Correct |
1 ms |
432 KB |
n=989 |
18 |
Correct |
1 ms |
332 KB |
n=563 |
19 |
Correct |
2 ms |
460 KB |
n=592 |
20 |
Correct |
2 ms |
440 KB |
n=938 |
21 |
Correct |
2 ms |
460 KB |
n=747 |
22 |
Correct |
2 ms |
440 KB |
n=991 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
463 ms |
94712 KB |
n=1000000 |
2 |
Correct |
250 ms |
59084 KB |
n=666666 |
3 |
Correct |
135 ms |
32932 KB |
n=400000 |
4 |
Correct |
310 ms |
61824 KB |
n=285714 |
5 |
Correct |
8 ms |
1720 KB |
n=20000 |
6 |
Correct |
278 ms |
49520 KB |
n=181818 |
7 |
Correct |
3 ms |
976 KB |
n=10000 |
8 |
Correct |
60 ms |
4932 KB |
n=6666 |
9 |
Correct |
2 ms |
588 KB |
n=4000 |
10 |
Correct |
166 ms |
25552 KB |
n=2857 |
11 |
Correct |
1 ms |
460 KB |
n=2000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
316 KB |
n=4 |
2 |
Correct |
1 ms |
204 KB |
n=3 |
3 |
Correct |
0 ms |
204 KB |
n=3 |
4 |
Correct |
1 ms |
320 KB |
n=4 |
5 |
Correct |
1 ms |
320 KB |
n=4 |
6 |
Correct |
0 ms |
204 KB |
n=2 |
7 |
Correct |
1 ms |
204 KB |
n=5 |
8 |
Correct |
1 ms |
204 KB |
n=8 |
9 |
Correct |
16 ms |
320 KB |
n=14 |
10 |
Correct |
1 ms |
204 KB |
n=11 |
11 |
Correct |
35 ms |
5308 KB |
n=50000 |
12 |
Correct |
24 ms |
5096 KB |
n=50000 |
13 |
Correct |
0 ms |
204 KB |
n=10 |
14 |
Correct |
1 ms |
332 KB |
n=685 |
15 |
Correct |
1 ms |
324 KB |
n=623 |
16 |
Correct |
1 ms |
332 KB |
n=973 |
17 |
Correct |
1 ms |
432 KB |
n=989 |
18 |
Correct |
1 ms |
332 KB |
n=563 |
19 |
Correct |
2 ms |
460 KB |
n=592 |
20 |
Correct |
2 ms |
440 KB |
n=938 |
21 |
Correct |
2 ms |
460 KB |
n=747 |
22 |
Correct |
2 ms |
440 KB |
n=991 |
23 |
Correct |
463 ms |
94712 KB |
n=1000000 |
24 |
Correct |
250 ms |
59084 KB |
n=666666 |
25 |
Correct |
135 ms |
32932 KB |
n=400000 |
26 |
Correct |
310 ms |
61824 KB |
n=285714 |
27 |
Correct |
8 ms |
1720 KB |
n=20000 |
28 |
Correct |
278 ms |
49520 KB |
n=181818 |
29 |
Correct |
3 ms |
976 KB |
n=10000 |
30 |
Correct |
60 ms |
4932 KB |
n=6666 |
31 |
Correct |
2 ms |
588 KB |
n=4000 |
32 |
Correct |
166 ms |
25552 KB |
n=2857 |
33 |
Correct |
1 ms |
460 KB |
n=2000 |
34 |
Correct |
17 ms |
3040 KB |
n=23514 |
35 |
Correct |
14 ms |
3076 KB |
n=23514 |
36 |
Correct |
1 ms |
320 KB |
n=940 |
37 |
Correct |
0 ms |
204 KB |
n=2 |
38 |
Correct |
73 ms |
16344 KB |
n=100000 |
39 |
Correct |
75 ms |
16428 KB |
n=100000 |
40 |
Correct |
1 ms |
204 KB |
n=10 |
41 |
Correct |
1 ms |
320 KB |
n=100 |
42 |
Correct |
5 ms |
972 KB |
n=1000 |
43 |
Correct |
561 ms |
122700 KB |
n=1000000 |
44 |
Correct |
606 ms |
133240 KB |
n=1000000 |
45 |
Correct |
458 ms |
103972 KB |
n=666666 |
46 |
Correct |
343 ms |
73748 KB |
n=400000 |
47 |
Correct |
150 ms |
25284 KB |
n=2336 |
48 |
Correct |
303 ms |
61772 KB |
n=285714 |
49 |
Correct |
246 ms |
49508 KB |
n=181818 |
50 |
Correct |
169 ms |
31552 KB |
n=40000 |
51 |
Correct |
207 ms |
28992 KB |
n=20000 |
52 |
Correct |
178 ms |
26748 KB |
n=10000 |
53 |
Correct |
159 ms |
26440 KB |
n=6666 |
54 |
Correct |
155 ms |
25776 KB |
n=4000 |
55 |
Correct |
150 ms |
25584 KB |
n=2857 |
56 |
Correct |
152 ms |
24540 KB |
n=2000 |