oj.uz

Submission #93296

# Submission time Handle Problem Language Result Execution time Memory
93296 2019-01-07T12:57:14 Z Abelyan Gift (IZhO18_nicegift) C++17
30 / 100
 443 ms 204100 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORR(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTR(i,a,b) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define fr first
#define sc second

const int N=1e6+6;
ll a[N],indcomp[N];
vector<pair<ll,int> > comp[N];
vector<int> ans[N];
int main(){
    ios_base::sync_with_stdio(false);
    ll n,k;
    cin>>n>>k;
    ll sum=0;
    ll mx=0;
    FOR(i,n){
        cin>>a[i];
        sum+=a[i];
        mx=max(mx,a[i]);
    }
    if (sum%k!=0 || sum/k<mx){
        cout<<-1<<endl;
        return 0;
    }
    ll tv=0,sahm=sum/k,cnt=0;
    FOR(i,n){
        if (!a[i])continue;
        if (tv+a[i]>=sahm){
            comp[cnt].push_back({sahm-tv,i+1});
            a[i]-=sahm-tv;
            cnt++;
            tv=0;
            i--;
            continue;
        }
        comp[cnt].push_back({a[i],i+1});
        tv+=a[i];
    }
    int hert=0;
    while(sum){
        //cout<<sum<<endl;
        ll mn=INT_MAX;
        FOR(i,k){
            mn=min(mn,comp[i][indcomp[i]].fr);
        }
        ans[hert].push_back(mn);
        FOR(i,k){
            comp[i][indcomp[i]].fr-=mn;
            ans[hert].push_back(comp[i][indcomp[i]].sc);
            if (comp[i][indcomp[i]].fr==0)
                indcomp[i]++;
        }
        hert++;
        sum-=(k*mn);
    }
    cout<<hert<<endl;
    FOR(i,hert){
        //cout<<ans[i].size()<<" ";
        trav(tt,ans[i])cout<<tt<<" ";
        cout<<endl;
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 47352 KB n=4
2 Correct 38 ms 47352 KB n=3
3 Correct 37 ms 47352 KB n=3
4 Correct 61 ms 47352 KB n=4
5 Correct 37 ms 47308 KB n=4
6 Correct 37 ms 47352 KB n=2

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 47352 KB n=4
2 Correct 38 ms 47352 KB n=3
3 Correct 37 ms 47352 KB n=3
4 Correct 61 ms 47352 KB n=4
5 Correct 37 ms 47308 KB n=4
6 Correct 37 ms 47352 KB n=2
7 Correct 36 ms 47352 KB n=5
8 Correct 36 ms 47352 KB n=8
9 Correct 37 ms 47352 KB n=14
10 Correct 37 ms 47352 KB n=11
11 Correct 116 ms 50480 KB n=50000
12 Correct 107 ms 50292 KB n=50000
13 Correct 38 ms 47352 KB n=10
14 Correct 45 ms 47356 KB n=685
15 Correct 38 ms 47352 KB n=623
16 Correct 39 ms 47352 KB n=973

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 47352 KB n=4
2 Correct 38 ms 47352 KB n=3
3 Correct 37 ms 47352 KB n=3
4 Correct 61 ms 47352 KB n=4
5 Correct 37 ms 47308 KB n=4
6 Correct 37 ms 47352 KB n=2
7 Correct 36 ms 47352 KB n=5
8 Correct 36 ms 47352 KB n=8
9 Correct 37 ms 47352 KB n=14
10 Correct 37 ms 47352 KB n=11
11 Correct 116 ms 50480 KB n=50000
12 Correct 107 ms 50292 KB n=50000
13 Correct 38 ms 47352 KB n=10
14 Correct 45 ms 47356 KB n=685
15 Correct 38 ms 47352 KB n=623
16 Correct 39 ms 47352 KB n=973
17 Correct 44 ms 47336 KB n=989
18 Correct 39 ms 47352 KB n=563
19 Correct 40 ms 47484 KB n=592
20 Correct 41 ms 47480 KB n=938
21 Correct 39 ms 47480 KB n=747
22 Correct 46 ms 47480 KB n=991

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 443 ms 204100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 47352 KB n=4
2 Correct 38 ms 47352 KB n=3
3 Correct 37 ms 47352 KB n=3
4 Correct 61 ms 47352 KB n=4
5 Correct 37 ms 47308 KB n=4
6 Correct 37 ms 47352 KB n=2
7 Correct 36 ms 47352 KB n=5
8 Correct 36 ms 47352 KB n=8
9 Correct 37 ms 47352 KB n=14
10 Correct 37 ms 47352 KB n=11
11 Correct 116 ms 50480 KB n=50000
12 Correct 107 ms 50292 KB n=50000
13 Correct 38 ms 47352 KB n=10
14 Correct 45 ms 47356 KB n=685
15 Correct 38 ms 47352 KB n=623
16 Correct 39 ms 47352 KB n=973
17 Correct 44 ms 47336 KB n=989
18 Correct 39 ms 47352 KB n=563
19 Correct 40 ms 47484 KB n=592
20 Correct 41 ms 47480 KB n=938
21 Correct 39 ms 47480 KB n=747
22 Correct 46 ms 47480 KB n=991
23 Runtime error 443 ms 204100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Halted 0 ms 0 KB -