oj.uz

Submission #77110

# Submission time Handle Problem Language Result Execution time Memory
77110 2018-09-22T07:14:40 Z zetapi Gift (IZhO18_nicegift) C++14
100 / 100
 1470 ms 254116 KB 
#include "bits/stdc++.h"
using namespace std;

#define pb  push_back
#define mp  make_pair
#define ll  long long
#define int long long
#define itr iterator

typedef pair<ll,ll> pii;

const ll MAX=2e6;
const ll INF=1e12;

vector<pii> vec;

vector<pair<ll,set<ll>>> res;

ll N,K,sum,mx,arr[MAX];

void insert(int X,int Y,int Z)
{
	vec.pb(mp(X,Z));
	vec.pb(mp(Y+1,-Z));
}

signed main()
{
	ios_base::sync_with_stdio(false);

	cin>>N>>K;
	for(int A=1;A<=N;A++)
	{
		cin>>arr[A];
		sum+=arr[A];
		mx=max(mx,arr[A]);
	}
	if(sum%K or mx>sum/K)
		return cout<<-1,0;
	int lst=1,row=K,col=sum/K;
	for(int A=1;A<=N;A++)
	{
		if(lst+arr[A]-1>col)
			insert(lst,col,A),
			insert(1,arr[A]-(col-lst+1),A);
		else
			insert(lst,lst+arr[A]-1,A);
		lst=(lst-1+arr[A])%col+1;
	}
	sort(vec.begin(),vec.end());
	int ptr=0;
	set<int> st;
	while(ptr<vec.size())
	{
		int cur=ptr;
		while(ptr<vec.size() and vec[cur].first==vec[ptr].first)
		{
			if(vec[ptr].second<0)
				st.erase(-vec[ptr].second);
			else
				st.insert(vec[ptr].second);
			++ptr;
		}
		if(ptr<vec.size())
			res.pb(mp(vec[ptr].first-vec[cur].first,st));
	}
	cout<<res.size()<<"\n";
	for(auto A:res)
	{
		cout<<A.first<<" ";
		for(auto B:A.second)
			cout<<B<<" ";
		cout<<"\n";
	}
	return 0;
}

Compilation message

nicegift.cpp: In function 'int main()':
nicegift.cpp:53:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ptr<vec.size())
        ~~~^~~~~~~~~~~
nicegift.cpp:56:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr<vec.size() and vec[cur].first==vec[ptr].first)
         ~~~^~~~~~~~~~~
nicegift.cpp:64:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ptr<vec.size())
      ~~~^~~~~~~~~~~
nicegift.cpp:40:12: warning: unused variable 'row' [-Wunused-variable]
  int lst=1,row=K,col=sum/K;
            ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n=4
2 Correct 2 ms 396 KB n=3
3 Correct 2 ms 604 KB n=3
4 Correct 2 ms 604 KB n=4
5 Correct 2 ms 604 KB n=4
6 Correct 2 ms 604 KB n=2

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n=4
2 Correct 2 ms 396 KB n=3
3 Correct 2 ms 604 KB n=3
4 Correct 2 ms 604 KB n=4
5 Correct 2 ms 604 KB n=4
6 Correct 2 ms 604 KB n=2
7 Correct 2 ms 604 KB n=5
8 Correct 2 ms 612 KB n=8
9 Correct 2 ms 640 KB n=14
10 Correct 2 ms 640 KB n=11
11 Correct 48 ms 9580 KB n=50000
12 Correct 47 ms 9580 KB n=50000
13 Correct 2 ms 9580 KB n=10
14 Correct 3 ms 9580 KB n=685
15 Correct 3 ms 9580 KB n=623
16 Correct 4 ms 9580 KB n=973

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n=4
2 Correct 2 ms 396 KB n=3
3 Correct 2 ms 604 KB n=3
4 Correct 2 ms 604 KB n=4
5 Correct 2 ms 604 KB n=4
6 Correct 2 ms 604 KB n=2
7 Correct 2 ms 604 KB n=5
8 Correct 2 ms 612 KB n=8
9 Correct 2 ms 640 KB n=14
10 Correct 2 ms 640 KB n=11
11 Correct 48 ms 9580 KB n=50000
12 Correct 47 ms 9580 KB n=50000
13 Correct 2 ms 9580 KB n=10
14 Correct 3 ms 9580 KB n=685
15 Correct 3 ms 9580 KB n=623
16 Correct 4 ms 9580 KB n=973
17 Correct 3 ms 9580 KB n=989
18 Correct 3 ms 9580 KB n=563
19 Correct 5 ms 9580 KB n=592
20 Correct 5 ms 9580 KB n=938
21 Correct 4 ms 9580 KB n=747
22 Correct 6 ms 9580 KB n=991

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 996 ms 138536 KB n=1000000
2 Correct 521 ms 138536 KB n=666666
3 Correct 309 ms 138536 KB n=400000
4 Correct 757 ms 154472 KB n=285714
5 Correct 20 ms 154472 KB n=20000
6 Correct 617 ms 154472 KB n=181818
7 Correct 12 ms 154472 KB n=10000
8 Correct 86 ms 154472 KB n=6666
9 Correct 5 ms 154472 KB n=4000
10 Correct 534 ms 154472 KB n=2857
11 Correct 5 ms 154472 KB n=2000

Subtask #5
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n=4
2 Correct 2 ms 396 KB n=3
3 Correct 2 ms 604 KB n=3
4 Correct 2 ms 604 KB n=4
5 Correct 2 ms 604 KB n=4
6 Correct 2 ms 604 KB n=2
7 Correct 2 ms 604 KB n=5
8 Correct 2 ms 612 KB n=8
9 Correct 2 ms 640 KB n=14
10 Correct 2 ms 640 KB n=11
11 Correct 48 ms 9580 KB n=50000
12 Correct 47 ms 9580 KB n=50000
13 Correct 2 ms 9580 KB n=10
14 Correct 3 ms 9580 KB n=685
15 Correct 3 ms 9580 KB n=623
16 Correct 4 ms 9580 KB n=973
17 Correct 3 ms 9580 KB n=989
18 Correct 3 ms 9580 KB n=563
19 Correct 5 ms 9580 KB n=592
20 Correct 5 ms 9580 KB n=938
21 Correct 4 ms 9580 KB n=747
22 Correct 6 ms 9580 KB n=991
23 Correct 996 ms 138536 KB n=1000000
24 Correct 521 ms 138536 KB n=666666
25 Correct 309 ms 138536 KB n=400000
26 Correct 757 ms 154472 KB n=285714
27 Correct 20 ms 154472 KB n=20000
28 Correct 617 ms 154472 KB n=181818
29 Correct 12 ms 154472 KB n=10000
30 Correct 86 ms 154472 KB n=6666
31 Correct 5 ms 154472 KB n=4000
32 Correct 534 ms 154472 KB n=2857
33 Correct 5 ms 154472 KB n=2000
34 Correct 29 ms 154472 KB n=23514
35 Correct 29 ms 154472 KB n=23514
36 Correct 3 ms 154472 KB n=940
37 Correct 2 ms 154472 KB n=2
38 Correct 184 ms 154472 KB n=100000
39 Correct 232 ms 154472 KB n=100000
40 Correct 3 ms 154472 KB n=10
41 Correct 3 ms 154472 KB n=100
42 Correct 14 ms 154472 KB n=1000
43 Correct 1179 ms 236940 KB n=1000000
44 Correct 1470 ms 254116 KB n=1000000
45 Correct 1145 ms 254116 KB n=666666
46 Correct 921 ms 254116 KB n=400000
47 Correct 521 ms 254116 KB n=2336
48 Correct 765 ms 254116 KB n=285714
49 Correct 631 ms 254116 KB n=181818
50 Correct 517 ms 254116 KB n=40000
51 Correct 536 ms 254116 KB n=20000
52 Correct 475 ms 254116 KB n=10000
53 Correct 479 ms 254116 KB n=6666
54 Correct 469 ms 254116 KB n=4000
55 Correct 525 ms 254116 KB n=2857
56 Correct 566 ms 254116 KB n=2000