# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
486091 | 2021-11-10T14:24:21 Z | Ronin13 | Gift (IZhO18_nicegift) | C++14 | 1422 ms | 524292 KB |
#include<bits/stdc++.h> #define ll long long #define ull unsigned ll #define pb push_back #define epb emplace_back #define f first #define s second #define pll pair<ll,ll> #define pii pair<int,int> #define inf 1e9+1 #define linf 1e18+1 using namespace std; void solve(){ int n;cin>>n; int k;cin>>k; ll a[n+1]; for(int i=1;i<=n;i++)cin>>a[i]; ll sum=0; ll mx=0; for(int i=1;i<=n;i++){ sum+=a[i]; mx=max(mx,a[i]); } if(sum%(ll)k){ cout<<-1<<"\n"; return; } if(mx>sum/(ll)k){ cout<<-1<<"\n"; return; } vector<vector<pll> >vec(k+1); int ind=1; for(int i=1;i<=k;i++){ ll left=sum/(ll)k; while(left>0){ if(left>=a[ind])vec[i].pb({a[ind],ind}),left-=a[ind],ind++; else{ a[ind]-=left,vec[i].pb({left,ind}); left=0; } } } vector<int>idx(k+1,0); vector<vector<ll> >ans; while(idx[1]<vec[1].size()){ ll mn=inf; for(int i=1;i<=k;i++){ int in=idx[i]; mn=min(mn,vec[i][in].f); } vector<ll>xx; xx.pb(mn); for(int i=1;i<=k;i++){ xx.pb(vec[i][idx[i]].s); } ans.pb(xx); for(int i=1;i<=k;i++){ int in=idx[i]; vec[i][in].f-=mn; if(vec[i][in].f==0)idx[i]++; } } cout<<ans.size()<<"\n"; for(int i=0;i<ans.size();i++){ for(int to:ans[i])cout<<to<<" "; cout<<"\n"; } } int main(){ ios_base::sync_with_stdio(false);cin.tie(0); int test=1;//cin>>test; while(test--){ solve(); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | n=4 |
2 | Correct | 0 ms | 204 KB | n=3 |
3 | Correct | 0 ms | 204 KB | n=3 |
4 | Correct | 0 ms | 204 KB | n=4 |
5 | Correct | 0 ms | 204 KB | n=4 |
6 | Correct | 1 ms | 248 KB | n=2 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | n=4 |
2 | Correct | 0 ms | 204 KB | n=3 |
3 | Correct | 0 ms | 204 KB | n=3 |
4 | Correct | 0 ms | 204 KB | n=4 |
5 | Correct | 0 ms | 204 KB | n=4 |
6 | Correct | 1 ms | 248 KB | n=2 |
7 | Correct | 1 ms | 204 KB | n=5 |
8 | Correct | 0 ms | 204 KB | n=8 |
9 | Correct | 0 ms | 204 KB | n=14 |
10 | Correct | 0 ms | 204 KB | n=11 |
11 | Correct | 22 ms | 4464 KB | n=50000 |
12 | Correct | 27 ms | 4280 KB | n=50000 |
13 | Correct | 1 ms | 204 KB | n=10 |
14 | Correct | 1 ms | 332 KB | n=685 |
15 | Correct | 1 ms | 332 KB | n=623 |
16 | Correct | 2 ms | 332 KB | n=973 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | n=4 |
2 | Correct | 0 ms | 204 KB | n=3 |
3 | Correct | 0 ms | 204 KB | n=3 |
4 | Correct | 0 ms | 204 KB | n=4 |
5 | Correct | 0 ms | 204 KB | n=4 |
6 | Correct | 1 ms | 248 KB | n=2 |
7 | Correct | 1 ms | 204 KB | n=5 |
8 | Correct | 0 ms | 204 KB | n=8 |
9 | Correct | 0 ms | 204 KB | n=14 |
10 | Correct | 0 ms | 204 KB | n=11 |
11 | Correct | 22 ms | 4464 KB | n=50000 |
12 | Correct | 27 ms | 4280 KB | n=50000 |
13 | Correct | 1 ms | 204 KB | n=10 |
14 | Correct | 1 ms | 332 KB | n=685 |
15 | Correct | 1 ms | 332 KB | n=623 |
16 | Correct | 2 ms | 332 KB | n=973 |
17 | Correct | 1 ms | 332 KB | n=989 |
18 | Correct | 1 ms | 332 KB | n=563 |
19 | Correct | 2 ms | 460 KB | n=592 |
20 | Correct | 2 ms | 460 KB | n=938 |
21 | Correct | 1 ms | 436 KB | n=747 |
22 | Correct | 2 ms | 460 KB | n=991 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1422 ms | 524292 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | n=4 |
2 | Correct | 0 ms | 204 KB | n=3 |
3 | Correct | 0 ms | 204 KB | n=3 |
4 | Correct | 0 ms | 204 KB | n=4 |
5 | Correct | 0 ms | 204 KB | n=4 |
6 | Correct | 1 ms | 248 KB | n=2 |
7 | Correct | 1 ms | 204 KB | n=5 |
8 | Correct | 0 ms | 204 KB | n=8 |
9 | Correct | 0 ms | 204 KB | n=14 |
10 | Correct | 0 ms | 204 KB | n=11 |
11 | Correct | 22 ms | 4464 KB | n=50000 |
12 | Correct | 27 ms | 4280 KB | n=50000 |
13 | Correct | 1 ms | 204 KB | n=10 |
14 | Correct | 1 ms | 332 KB | n=685 |
15 | Correct | 1 ms | 332 KB | n=623 |
16 | Correct | 2 ms | 332 KB | n=973 |
17 | Correct | 1 ms | 332 KB | n=989 |
18 | Correct | 1 ms | 332 KB | n=563 |
19 | Correct | 2 ms | 460 KB | n=592 |
20 | Correct | 2 ms | 460 KB | n=938 |
21 | Correct | 1 ms | 436 KB | n=747 |
22 | Correct | 2 ms | 460 KB | n=991 |
23 | Runtime error | 1422 ms | 524292 KB | Execution killed with signal 9 |
24 | Halted | 0 ms | 0 KB | - |