oj.uz

Submission #378859

# Submission time Handle Problem Language Result Execution time Memory
378859 2021-03-17T06:21:51 Z YJU Gift (IZhO18_nicegift) C++14
100 / 100
 1120 ms 89836 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=2e6+5;
const ll MOD=1e9+7;
const ll INF=(1LL<<60);
const ld pi=acos(-1);
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define lwb lower_bound
#define ALL(_a) _a.begin(),_a.end()
#define SZ(_a) (ll)_a.size()

ll n,k,u[N],sum;
priority_queue<pll> pq;
vector<pair<ll,vector<ll> > > ans;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    REP1(i,n)cin>>u[i],pq.push(mp(u[i],i)),sum+=u[i];
    while(SZ(pq)>=k){
		vector<ll> cho;
		ll mx1,mx2;
        REP(i,k){
			pll nd=pq.top();
			mx1=nd.X;
			cho.pb(nd.Y);
            pq.pop();
        }
        mx2=pq.top().X;
        ll x=min(mx1,(SZ(pq)?(sum-mx2*k)/k:INF));
        ans.pb(mp(x,cho));
        sum-=x*k;
        REP(i,k){
			u[cho[i]]-=x;
			if(u[cho[i]])pq.push(mp(u[cho[i]],cho[i]));
        }
    }
	if(!SZ(pq)){
		cout<<SZ(ans)<<"\n";
		for(auto i:ans){
			cout<<i.X;
			for(auto j:i.Y)cout<<" "<<j;
			cout<<"\n";
		}
	}else{
		cout<<"-1\n";
	}
	return 0;
}

Compilation message

nicegift.cpp: In function 'int main()':
nicegift.cpp:31:6: warning: 'mx1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |   ll mx1,mx2;
      |      ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB n=4
2 Correct 1 ms 364 KB n=3
3 Correct 1 ms 384 KB n=3
4 Correct 1 ms 364 KB n=4
5 Correct 1 ms 364 KB n=4
6 Correct 1 ms 364 KB n=2

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB n=4
2 Correct 1 ms 364 KB n=3
3 Correct 1 ms 384 KB n=3
4 Correct 1 ms 364 KB n=4
5 Correct 1 ms 364 KB n=4
6 Correct 1 ms 364 KB n=2
7 Correct 1 ms 364 KB n=5
8 Correct 1 ms 364 KB n=8
9 Correct 1 ms 364 KB n=14
10 Correct 1 ms 364 KB n=11
11 Correct 25 ms 4072 KB n=50000
12 Correct 22 ms 3896 KB n=50000
13 Correct 1 ms 364 KB n=10
14 Correct 1 ms 364 KB n=685
15 Correct 1 ms 364 KB n=623
16 Correct 1 ms 364 KB n=973

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB n=4
2 Correct 1 ms 364 KB n=3
3 Correct 1 ms 384 KB n=3
4 Correct 1 ms 364 KB n=4
5 Correct 1 ms 364 KB n=4
6 Correct 1 ms 364 KB n=2
7 Correct 1 ms 364 KB n=5
8 Correct 1 ms 364 KB n=8
9 Correct 1 ms 364 KB n=14
10 Correct 1 ms 364 KB n=11
11 Correct 25 ms 4072 KB n=50000
12 Correct 22 ms 3896 KB n=50000
13 Correct 1 ms 364 KB n=10
14 Correct 1 ms 364 KB n=685
15 Correct 1 ms 364 KB n=623
16 Correct 1 ms 364 KB n=973
17 Correct 1 ms 364 KB n=989
18 Correct 1 ms 364 KB n=563
19 Correct 1 ms 364 KB n=592
20 Correct 1 ms 364 KB n=938
21 Correct 1 ms 364 KB n=747
22 Correct 1 ms 364 KB n=991

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 70972 KB n=1000000
2 Correct 366 ms 40548 KB n=666666
3 Correct 201 ms 22480 KB n=400000
4 Correct 139 ms 14936 KB n=285714
5 Correct 9 ms 1392 KB n=20000
6 Correct 85 ms 9692 KB n=181818
7 Correct 6 ms 1004 KB n=10000
8 Correct 4 ms 748 KB n=6666
9 Correct 2 ms 620 KB n=4000
10 Correct 4 ms 748 KB n=2857
11 Correct 1 ms 492 KB n=2000

Subtask #5
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB n=4
2 Correct 1 ms 364 KB n=3
3 Correct 1 ms 384 KB n=3
4 Correct 1 ms 364 KB n=4
5 Correct 1 ms 364 KB n=4
6 Correct 1 ms 364 KB n=2
7 Correct 1 ms 364 KB n=5
8 Correct 1 ms 364 KB n=8
9 Correct 1 ms 364 KB n=14
10 Correct 1 ms 364 KB n=11
11 Correct 25 ms 4072 KB n=50000
12 Correct 22 ms 3896 KB n=50000
13 Correct 1 ms 364 KB n=10
14 Correct 1 ms 364 KB n=685
15 Correct 1 ms 364 KB n=623
16 Correct 1 ms 364 KB n=973
17 Correct 1 ms 364 KB n=989
18 Correct 1 ms 364 KB n=563
19 Correct 1 ms 364 KB n=592
20 Correct 1 ms 364 KB n=938
21 Correct 1 ms 364 KB n=747
22 Correct 1 ms 364 KB n=991
23 Correct 573 ms 70972 KB n=1000000
24 Correct 366 ms 40548 KB n=666666
25 Correct 201 ms 22480 KB n=400000
26 Correct 139 ms 14936 KB n=285714
27 Correct 9 ms 1392 KB n=20000
28 Correct 85 ms 9692 KB n=181818
29 Correct 6 ms 1004 KB n=10000
30 Correct 4 ms 748 KB n=6666
31 Correct 2 ms 620 KB n=4000
32 Correct 4 ms 748 KB n=2857
33 Correct 1 ms 492 KB n=2000
34 Correct 17 ms 2540 KB n=23514
35 Correct 16 ms 2540 KB n=23514
36 Correct 1 ms 492 KB n=940
37 Correct 1 ms 364 KB n=2
38 Correct 47 ms 5604 KB n=100000
39 Correct 46 ms 5604 KB n=100000
40 Correct 1 ms 364 KB n=10
41 Correct 1 ms 364 KB n=100
42 Correct 3 ms 492 KB n=1000
43 Correct 690 ms 86272 KB n=1000000
44 Correct 1120 ms 89836 KB n=1000000
45 Correct 753 ms 56260 KB n=666666
46 Correct 425 ms 31824 KB n=400000
47 Correct 11 ms 1132 KB n=2336
48 Correct 736 ms 49216 KB n=285714
49 Correct 616 ms 41812 KB n=181818
50 Correct 30 ms 2792 KB n=40000
51 Correct 16 ms 1644 KB n=20000
52 Correct 9 ms 1136 KB n=10000
53 Correct 63 ms 4460 KB n=6666
54 Correct 5 ms 748 KB n=4000
55 Correct 247 ms 16492 KB n=2857
56 Correct 3 ms 620 KB n=2000