oj.uz

Submission #486098

# Submission time Handle Problem Language Result Execution time Memory
486098 2021-11-10T14:36:32 Z Ronin13 Gift (IZhO18_nicegift) C++14
100 / 100
 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

nicegift.cpp: In function 'void solve()':
nicegift.cpp:49:17: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while(idx[1]<vec[1].size()){

Subtask #1
7.0 / 7.0

# 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

Subtask #2
11.0 / 11.0

# 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 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

Subtask #3
12.0 / 12.0

# 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 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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory 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

Subtask #5
51.0 / 51.0

# 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 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