oj.uz

Submission #93299

# Submission time Handle Problem Language Result Execution time Memory
93299 2019-01-07T13:25:26 Z Abelyan Gift (IZhO18_nicegift) C++17
100 / 100
 1925 ms 203368 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=2e6+6;
ll a[N],indcomp[N];
vector<pair<ll,int> > comp[N];
vector<ll> 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];
        //cout<<a[i]<<endl;
        sum+=a[i];
        mx=max(mx,(ll)a[i]);
    }
    //cout<<sum<<endl;
    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+=(ll)a[i];
    }
    int hert=0;
    while(sum){
        //cout<<sum<<endl;
        ll mn=LLONG_MAX;
        FOR(i,k){
            if (indcomp[i]>=comp[i].size()){cout<<"hoy"<<endl;continue;}
            mn=min(mn,comp[i][indcomp[i]].fr);
        }
        ans[hert].push_back(mn);
        FOR(i,k){
            if (indcomp[i]>=comp[i].size()){cout<<"hoy"<<endl;continue;}
            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++;
        //if (hert>=N)break;
        sum-=(k*(ll)mn);
        //cout<<sum<<endl;
    }
    //cout<<sum<<endl;
    cout<<hert<<endl;
    FOR(i,hert){
        //cout<<ans[i].size()<<" ";
        trav(tt,ans[i])cout<<tt<<" ";
        cout<<endl;
    }
    return 0;
}

Compilation message

nicegift.cpp: In function 'int main()':
nicegift.cpp:57:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (indcomp[i]>=comp[i].size()){cout<<"hoy"<<endl;continue;}
                 ~~~~~~~~~~^~~~~~~~~~~~~~~~
nicegift.cpp:62:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (indcomp[i]>=comp[i].size()){cout<<"hoy"<<endl;continue;}
                 ~~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 94328 KB n=4
2 Correct 87 ms 94328 KB n=3
3 Correct 83 ms 94328 KB n=3
4 Correct 85 ms 94328 KB n=4
5 Correct 84 ms 94328 KB n=4
6 Correct 85 ms 94280 KB n=2

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 94328 KB n=4
2 Correct 87 ms 94328 KB n=3
3 Correct 83 ms 94328 KB n=3
4 Correct 85 ms 94328 KB n=4
5 Correct 84 ms 94328 KB n=4
6 Correct 85 ms 94280 KB n=2
7 Correct 87 ms 94328 KB n=5
8 Correct 86 ms 94328 KB n=8
9 Correct 84 ms 94320 KB n=14
10 Correct 85 ms 94200 KB n=11
11 Correct 161 ms 98180 KB n=50000
12 Correct 156 ms 97904 KB n=50000
13 Correct 86 ms 94316 KB n=10
14 Correct 88 ms 94460 KB n=685
15 Correct 87 ms 94328 KB n=623
16 Correct 89 ms 94328 KB n=973

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 94328 KB n=4
2 Correct 87 ms 94328 KB n=3
3 Correct 83 ms 94328 KB n=3
4 Correct 85 ms 94328 KB n=4
5 Correct 84 ms 94328 KB n=4
6 Correct 85 ms 94280 KB n=2
7 Correct 87 ms 94328 KB n=5
8 Correct 86 ms 94328 KB n=8
9 Correct 84 ms 94320 KB n=14
10 Correct 85 ms 94200 KB n=11
11 Correct 161 ms 98180 KB n=50000
12 Correct 156 ms 97904 KB n=50000
13 Correct 86 ms 94316 KB n=10
14 Correct 88 ms 94460 KB n=685
15 Correct 87 ms 94328 KB n=623
16 Correct 89 ms 94328 KB n=973
17 Correct 87 ms 94352 KB n=989
18 Correct 85 ms 94456 KB n=563
19 Correct 88 ms 94524 KB n=592
20 Correct 88 ms 94428 KB n=938
21 Correct 85 ms 94480 KB n=747
22 Correct 88 ms 94540 KB n=991

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1101 ms 155436 KB n=1000000
2 Correct 602 ms 131012 KB n=666666
3 Correct 319 ms 116568 KB n=400000
4 Correct 751 ms 143288 KB n=285714
5 Correct 94 ms 95480 KB n=20000
6 Correct 582 ms 141684 KB n=181818
7 Correct 90 ms 94840 KB n=10000
8 Correct 121 ms 100728 KB n=6666
9 Correct 90 ms 94492 KB n=4000
10 Correct 255 ms 126464 KB n=2857
11 Correct 87 ms 94456 KB n=2000

Subtask #5
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 94328 KB n=4
2 Correct 87 ms 94328 KB n=3
3 Correct 83 ms 94328 KB n=3
4 Correct 85 ms 94328 KB n=4
5 Correct 84 ms 94328 KB n=4
6 Correct 85 ms 94280 KB n=2
7 Correct 87 ms 94328 KB n=5
8 Correct 86 ms 94328 KB n=8
9 Correct 84 ms 94320 KB n=14
10 Correct 85 ms 94200 KB n=11
11 Correct 161 ms 98180 KB n=50000
12 Correct 156 ms 97904 KB n=50000
13 Correct 86 ms 94316 KB n=10
14 Correct 88 ms 94460 KB n=685
15 Correct 87 ms 94328 KB n=623
16 Correct 89 ms 94328 KB n=973
17 Correct 87 ms 94352 KB n=989
18 Correct 85 ms 94456 KB n=563
19 Correct 88 ms 94524 KB n=592
20 Correct 88 ms 94428 KB n=938
21 Correct 85 ms 94480 KB n=747
22 Correct 88 ms 94540 KB n=991
23 Correct 1101 ms 155436 KB n=1000000
24 Correct 602 ms 131012 KB n=666666
25 Correct 319 ms 116568 KB n=400000
26 Correct 751 ms 143288 KB n=285714
27 Correct 94 ms 95480 KB n=20000
28 Correct 582 ms 141684 KB n=181818
29 Correct 90 ms 94840 KB n=10000
30 Correct 121 ms 100728 KB n=6666
31 Correct 90 ms 94492 KB n=4000
32 Correct 255 ms 126464 KB n=2857
33 Correct 87 ms 94456 KB n=2000
34 Correct 130 ms 96544 KB n=23514
35 Correct 130 ms 96500 KB n=23514
36 Correct 79 ms 94328 KB n=940
37 Correct 86 ms 94332 KB n=2
38 Correct 289 ms 108132 KB n=100000
39 Correct 287 ms 107916 KB n=100000
40 Correct 86 ms 94200 KB n=10
41 Correct 86 ms 94328 KB n=100
42 Correct 92 ms 95096 KB n=1000
43 Correct 1894 ms 192828 KB n=1000000
44 Correct 1925 ms 203368 KB n=1000000
45 Correct 1374 ms 171344 KB n=666666
46 Correct 945 ms 157912 KB n=400000
47 Correct 246 ms 122072 KB n=2336
48 Correct 753 ms 144272 KB n=285714
49 Correct 581 ms 141940 KB n=181818
50 Correct 328 ms 128188 KB n=40000
51 Correct 337 ms 126324 KB n=20000
52 Correct 251 ms 124536 KB n=10000
53 Correct 250 ms 130936 KB n=6666
54 Correct 253 ms 119800 KB n=4000
55 Correct 253 ms 126472 KB n=2857
56 Correct 239 ms 118596 KB n=2000