# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
486098 | 2021-11-10T14:36:32 Z | Ronin13 | Gift (IZhO18_nicegift) | C++14 | 559 ms | 133412 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(n+1); ind=0; while(idx[1]<vec[1].size()){ ll mn=linf; for(int i=1;i<=k;i++){ int in=idx[i]; mn=min(mn,vec[i][in].f); } vector<ll>xx; ans[ind].pb(mn); for(int i=1;i<=k;i++){ ans[ind].pb(vec[i][idx[i]].s); } for(int i=1;i<=k;i++){ int in=idx[i]; vec[i][in].f-=mn; if(vec[i][in].f==0)idx[i]++; } ind++; } cout<<ind<<"\n"; for(int i=0;i<ind;i++){ for(ll 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
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 | 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 | 18 ms | 5220 KB | n=50000 |
12 | Correct | 17 ms | 5152 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 | 1 ms | 384 KB | n=973 |
# | 결과 | 실행 시간 | 메모리 | 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 | 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 | 18 ms | 5220 KB | n=50000 |
12 | Correct | 17 ms | 5152 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 | 1 ms | 384 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 | 460 KB | n=747 |
22 | Correct | 1 ms | 460 KB | n=991 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 332 ms | 85120 KB | n=1000000 |
2 | Correct | 202 ms | 59088 KB | n=666666 |
3 | Correct | 129 ms | 34628 KB | n=400000 |
4 | Correct | 273 ms | 57224 KB | n=285714 |
5 | Correct | 5 ms | 1868 KB | n=20000 |
6 | Correct | 228 ms | 52260 KB | n=181818 |
7 | Correct | 3 ms | 1100 KB | n=10000 |
8 | Correct | 26 ms | 6980 KB | n=6666 |
9 | Correct | 1 ms | 588 KB | n=4000 |
10 | Correct | 143 ms | 32724 KB | n=2857 |
11 | Correct | 1 ms | 460 KB | n=2000 |
# | 결과 | 실행 시간 | 메모리 | 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 | 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 | 18 ms | 5220 KB | n=50000 |
12 | Correct | 17 ms | 5152 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 | 1 ms | 384 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 | 460 KB | n=747 |
22 | Correct | 1 ms | 460 KB | n=991 |
23 | Correct | 332 ms | 85120 KB | n=1000000 |
24 | Correct | 202 ms | 59088 KB | n=666666 |
25 | Correct | 129 ms | 34628 KB | n=400000 |
26 | Correct | 273 ms | 57224 KB | n=285714 |
27 | Correct | 5 ms | 1868 KB | n=20000 |
28 | Correct | 228 ms | 52260 KB | n=181818 |
29 | Correct | 3 ms | 1100 KB | n=10000 |
30 | Correct | 26 ms | 6980 KB | n=6666 |
31 | Correct | 1 ms | 588 KB | n=4000 |
32 | Correct | 143 ms | 32724 KB | n=2857 |
33 | Correct | 1 ms | 460 KB | n=2000 |
34 | Correct | 11 ms | 3020 KB | n=23514 |
35 | Correct | 16 ms | 3028 KB | n=23514 |
36 | Correct | 1 ms | 320 KB | n=940 |
37 | Correct | 0 ms | 204 KB | n=2 |
38 | Correct | 66 ms | 16436 KB | n=100000 |
39 | Correct | 64 ms | 16340 KB | n=100000 |
40 | Correct | 0 ms | 204 KB | n=10 |
41 | Correct | 1 ms | 332 KB | n=100 |
42 | Correct | 4 ms | 1100 KB | n=1000 |
43 | Correct | 448 ms | 122640 KB | n=1000000 |
44 | Correct | 559 ms | 133412 KB | n=1000000 |
45 | Correct | 386 ms | 93480 KB | n=666666 |
46 | Correct | 299 ms | 73656 KB | n=400000 |
47 | Correct | 136 ms | 28312 KB | n=2336 |
48 | Correct | 261 ms | 57284 KB | n=285714 |
49 | Correct | 226 ms | 52332 KB | n=181818 |
50 | Correct | 158 ms | 35380 KB | n=40000 |
51 | Correct | 152 ms | 32964 KB | n=20000 |
52 | Correct | 145 ms | 30936 KB | n=10000 |
53 | Correct | 144 ms | 37308 KB | n=6666 |
54 | Correct | 160 ms | 26028 KB | n=4000 |
55 | Correct | 142 ms | 32708 KB | n=2857 |
56 | Correct | 140 ms | 24900 KB | n=2000 |