CSES - IZhO 2018, day 1 - Results
Submission details
Task:Gift
Sender:Olli
Submission time:2019-02-16 17:08:35 +0200
Language:C++
Status:READY
Result:49
Feedback
groupverdictscore
#1ACCEPTED7
#2ACCEPTED11
#3ACCEPTED12
#4ACCEPTED19
#50
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1, 2, 3, 5details
#2ACCEPTED0.06 s1, 2, 3, 5details
#3ACCEPTED0.06 s1, 2, 3, 5details
#4ACCEPTED0.06 s1, 2, 3, 5details
#5ACCEPTED0.06 s1, 2, 3, 5details
#6ACCEPTED0.04 s1, 2, 3, 5details
#7ACCEPTED0.05 s1, 2, 3, 5details
#8ACCEPTED0.05 s2, 3, 5details
#9ACCEPTED0.05 s2, 3, 5details
#10ACCEPTED0.05 s2, 3, 5details
#11ACCEPTED0.09 s2, 3, 5details
#12ACCEPTED0.08 s2, 3, 5details
#13ACCEPTED0.05 s2, 3, 5details
#14ACCEPTED0.05 s2, 3, 5details
#15ACCEPTED0.06 s2, 3, 5details
#16ACCEPTED0.05 s2, 3, 5details
#17ACCEPTED0.05 s3, 5details
#18ACCEPTED0.05 s3, 5details
#19ACCEPTED0.05 s3, 5details
#20ACCEPTED0.06 s3, 5details
#21ACCEPTED0.05 s3, 5details
#22ACCEPTED0.05 s3, 5details
#23ACCEPTED0.92 s4, 5details
#24ACCEPTED0.59 s4, 5details
#25ACCEPTED0.36 s4, 5details
#26ACCEPTED0.26 s4, 5details
#27ACCEPTED0.07 s4, 5details
#28ACCEPTED0.19 s4, 5details
#29ACCEPTED0.06 s4, 5details
#30ACCEPTED0.06 s4, 5details
#31ACCEPTED0.05 s4, 5details
#32ACCEPTED0.06 s4, 5details
#33ACCEPTED0.06 s4, 5details
#34ACCEPTED0.08 s5details
#35ACCEPTED0.08 s5details
#36ACCEPTED0.05 s5details
#37ACCEPTED0.05 s4, 5details
#38ACCEPTED0.13 s5details
#39ACCEPTED0.12 s5details
#400.43 s5details
#410.43 s5details
#42ACCEPTED0.07 s5details
#43ACCEPTED1.16 s5details
#44--5details
#45ACCEPTED1.52 s5details
#46ACCEPTED0.90 s5details
#47ACCEPTED0.06 s5details
#48ACCEPTED1.01 s5details
#49ACCEPTED0.77 s5details
#50ACCEPTED0.11 s5details
#51ACCEPTED0.08 s5details
#52ACCEPTED0.06 s5details
#53ACCEPTED0.14 s5details
#54ACCEPTED0.07 s5details
#55ACCEPTED0.37 s5details
#560.53 s5details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:113:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(s.size() == k) {
       ~~~~~~~~~^~~~
input/code.cpp:169:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < ne.size(); ++i) {
                   ~~^~~~~~~~~~~
input/code.cpp:188:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < mov[i].size(); ++j) {
                  ~~^~~~~~~~~~~~~~~

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <math.h>

using namespace std;

const int N = 1e6 + 5;
const int M = 131072;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define F first
#define S second

ll t[N];

set<pll> s;

vector<ll> mov[2*N];


int main() {
/*	set<int> se;
	for(int i = 1; i <= 10; ++i) {
		se.insert(i);
	}
	int cou = 3;
	int ii = 0;
	set<int>::iterator iter = se.begin();
	while(ii < cou) {
		se.erase(iter);
		cout << *iter << "\n";
		se.insert((*iter) - 3);
		++ii;
		++iter;
	}

	for(iter = se.begin(); iter != se.end(); ++iter) {
		cout << *iter << " ";
	}
	cout << "\n";
	return 0;
*/	

	cin.tie(0);
	iostream::sync_with_stdio(false);
	int n, k;
	cin >> n >> k;
	ll sum = 0;
	for(int i = 1; i <= n; ++i) {
		ll a; cin >> a; t[i] = a;
		s.insert({a, i});
		sum += a;
	}

	if(sum%k != 0) {
		cout << -1 << "\n";
		return 0;
	}

	for(int i = 1; i <= n; ++i) {
		if(t[i] > sum/k) {
			cout << -1 << "\n";
			return 0;
		}
	}

	if(n == k) {
		for(int i = 1; i <= n; ++i) {
			if(t[i] != sum/k) {
				cout << -1 << "\n";
				return 0;
			}
		}
		cout << 1 << "\n";
		cout << sum/k << " ";
		for(int i = 1; i <= n; ++i) {
			cout << i << " ";
		}
		cout << "\n";
		return 0;
	}

	ll c = 0;
	
	if(k >= 1e7) {
		vector<pll> v;
		v.push_back({-1, -1});
		for(int i = 1; i <= n; ++i) {
			v.push_back({t[i], i});
		}
		sort(v.begin(), v.end());
		while(sum > 0 && c*k <= 3000000) {
			ll x = min(sum/k - v[n-k].first, v[n-k+1].first);
			mov[c].push_back(x);
			for(int i = n-k+1; i <= n; ++i) {
				v[i] = {v[i].first - x, v[i].second};
				mov[c].push_back(v[i].second);
			}
			sort(v.begin(), v.end());
			sum -= x*k;
			++c;
		}
	} else {
		while(sum > 0 && c*k <= 3000000) {
			ll k1th = -1;
			set<pll>::iterator it;
			if(s.size() == k) {
				k1th = 0;
			} else {
				if(k < n/2) {
					it = s.end();
					--it;
					int i = n;
					while(i != n - k) {
						--it;
						--i;
					}
				} else {
					it = s.begin();
					int i = 1;
					while(i != n-k) {
						++it;
						++i;
					}
				}
			}

			if(k1th == -1) {
				k1th = (*it).first;
				++it;
			} else {
				it = s.begin();
			}
		//	cout << "Sum : " << sum << " and k+1:th largest is " << k1th << "\n";
			ll x = min(sum/k - k1th, (*it).first);
			it = s.end();
			vector<pll> ne;
			mov[c].push_back(x);
			for(int i = n; i > n-k; --i) {
				--it;
				ne.push_back({(*it).first - x, (*it).second});
				mov[c].push_back((*it).second);
			}
	
	//	cout << "Sum : " << sum << " and k+1:th largest is " << k1th << "\n";
	/*		ll x = min(sum/k - k1th, (*it).first);
			mov[c].push_back(x);
			for(int i = n - k + 1; i <= n; ++i) {
				if((*it).first != x) {
					s.insert({(*it).first - x, (*it).second});
				}
				mov[c].push_back((*it).second);
				set<pll>::iterator ite = it;
				++it;
				s.erase(ite);
			}
*/
			for(int i = n; i > n-k; --i) {
				it = s.end();
				--it;
				s.erase(it);	
			}
			for(int i = 0; i < ne.size(); ++i) {
				if(ne[i].first != 0) {
					s.insert(ne[i]);
				}
			}
			sum -= x*k;
			++c;
		}
		if(sum != 0) {
			cout << -1 << "\n";
			return 0;
			while(true) {
				cout << "ABBACD\n";
			}		
		}
	}

	cout << c << "\n";
	for(int i = 0; i < c; ++i) {
		for(int j = 0; j < mov[i].size(); ++j) {
			cout << mov[i][j] << " ";
		}
		cout << "\n";
	}
}

Test details

Test 1

Group: 1, 2, 3, 5

Verdict: ACCEPTED

input
4 2
2 3 3 2

correct output
3
2 3 1
1 3 2
2 2 4

user output
2
3 3 2 
2 4 1 

Test 2

Group: 1, 2, 3, 5

Verdict: ACCEPTED

input
3 2
2 1 1

correct output
2
1 1 2 
1 1 3 

user output
2
1 1 3 
1 2 1 

Test 3

Group: 1, 2, 3, 5

Verdict: ACCEPTED

input
3 2
1 2 4

correct output
-1

user output
-1

Test 4

Group: 1, 2, 3, 5

Verdict: ACCEPTED

input
4 2
1 2 3 4

correct output
3
1 1 3 
2 2 4 
2 3 4 

user output
3
3 4 3 
1 2 4 
1 2 1 

Test 5

Group: 1, 2, 3, 5

Verdict: ACCEPTED

input
4 2
1 2 1 5

correct output
-1

user output
-1

Test 6

Group: 1, 2, 3, 5

Verdict: ACCEPTED

input
2 2
4 5

correct output
-1

user output
-1

Test 7

Group: 1, 2, 3, 5

Verdict: ACCEPTED

input
5 2
2 1 3 1 1

correct output
3
2 1 3 
1 2 4 
1 3 5 

user output
3
2 3 1 
1 5 4 
1 3 2 

Test 8

Group: 2, 3, 5

Verdict: ACCEPTED

input
8 2
1 1 9101 17 161 57013 7 567

correct output
-1

user output
-1

Test 9

Group: 2, 3, 5

Verdict: ACCEPTED

input
14 2
36 117 358 64 1319 1355 5322 5...

correct output
14
36 1 12 
117 2 12 
358 3 12 
64 4 12 
...

user output
14
6012 13 12 
5294 7 13 
1319 6 5 
670 14 10 
...
Truncated

Test 10

Group: 2, 3, 5

Verdict: ACCEPTED

input
11 2
1 7192 2 49 3973 1 1 68 5274 6...

correct output
11
1 1 5 
2586 2 5 
1 2 6 
1 2 7 
...

user output
11
4657 2 9 
2535 5 2 
698 5 10 
617 5 9 
...
Truncated

Test 11

Group: 2, 3, 5

Verdict: ACCEPTED

input
50000 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
42250
1 1 33212 
1 2 33212 
1 3 33212 
1 4 33212 
...

user output
30104
18581 33212 41667 
706 33212 17435 
553 33212 3767 
53 33212 31460 
...
Truncated

Test 12

Group: 2, 3, 5

Verdict: ACCEPTED

input
50000 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
40020
1 1 27450 
1 2 27450 
1 3 27450 
1 4 27450 
...

user output
25007
10548 35035 5675 
4640 22494 35035 
3932 35120 27450 
3055 22494 37080 
...
Truncated

Test 13

Group: 2, 3, 5

Verdict: ACCEPTED

input
10 2
2730 1860 241 33771 20985 1391...

correct output
10
2730 1 5 
1860 2 5 
241 3 5 
4756 4 5 
...

user output
10
29015 4 10 
7899 5 9 
4756 5 4 
2730 5 1 
...
Truncated

Test 14

Group: 2, 3, 5

Verdict: ACCEPTED

input
685 2
118 132 114 115 123 136 122 10...

correct output
683
21 1 340 
97 1 341 
36 2 341 
96 2 342 
...

user output
379
158 123 513 
153 384 80 
149 87 479 
147 262 634 
...
Truncated

Test 15

Group: 2, 3, 5

Verdict: ACCEPTED

input
623 2
150 137 159 157 138 153 137 14...

correct output
622
77 1 312 
73 1 313 
72 2 313 
65 2 314 
...

user output
339
180 582 398 
178 30 426 
177 26 533 
176 467 261 
...
Truncated

Test 16

Group: 2, 3, 5

Verdict: ACCEPTED

input
973 2
58 52 54 57 52 71 46 58 64 45 ...

correct output
963
48 1 490 
10 1 491 
44 2 491 
8 2 492 
...

user output
509
74 892 304 
71 849 6 
70 929 549 
69 389 861 
...
Truncated

Test 17

Group: 3, 5

Verdict: ACCEPTED

input
989 3
102 100 91 75 103 79 85 83 98 ...

correct output
982
10 1 328 659 
33 1 329 659 
59 1 329 660 
4 2 329 660 
...

user output
383
126 316 170 855 
123 431 814 203 
121 127 196 686 
121 605 299 273 
...
Truncated

Test 18

Group: 3, 5

Verdict: ACCEPTED

input
563 8
91 104 85 106 99 84 94 118 94 ...

correct output
547
21 1 71 143 213 283 355 425 49...

user output
101
116 257 523 473 263 8 533 285 ...
Truncated

Test 19

Group: 3, 5

Verdict: ACCEPTED

input
592 23
161 178 166 168 144 152 152 16...

correct output
547
6 1 26 52 78 104 130 156 182 2...

user output
78
183 94 396 426 200 543 498 475...
Truncated

Test 20

Group: 3, 5

Verdict: ACCEPTED

input
938 15
102 104 89 123 105 111 90 98 9...

correct output
871
5 1 62 125 188 251 313 377 439...

user output
104
120 931 107 217 94 684 929 4 5...
Truncated

Test 21

Group: 3, 5

Verdict: ACCEPTED

input
747 10
96 88 99 82 108 68 82 110 97 8...

correct output
704
16 1 74 149 224 298 373 449 52...

user output
125
113 638 172 18 537 649 313 685...
Truncated

Test 22

Group: 3, 5

Verdict: ACCEPTED

input
991 13
83 76 94 77 76 88 79 91 85 69 ...

correct output
930
17 1 76 152 229 305 381 458 53...

user output
105
98 739 37 171 940 835 429 22 1...
Truncated

Test 23

Group: 4, 5

Verdict: ACCEPTED

input
1000000 2
1000000000000 1000000000000 10...

correct output
500000
1000000000000 1 500001 
1000000000000 2 500002 
1000000000000 3 500003 
1000000000000 4 500004 
...

user output
500000
1000000000000 1000000 999999 
1000000000000 999998 999997 
1000000000000 999996 999

...
Truncated

Test 24

Group: 4, 5

Verdict: ACCEPTED

input
666666 3
1500001500001 1500001500001 15...

correct output
222222
1500001500001 1 222223 444445 ...

user output
222222
1500001500001 666666 666665 66...
Truncated

Test 25

Group: 4, 5

Verdict: ACCEPTED

input
400000 5
2500000000000 2500000000000 25...

correct output
80000
2500000000000 1 80001 160001 2...

user output
80000
2500000000000 400000 399999 39...
Truncated

Test 26

Group: 4, 5

Verdict: ACCEPTED

input
285714 7
3500003500000 3500003500000 35...

correct output
285714
500000500000 1 40817 81633 122...

user output
40821
3500003500000 285714 285713 28...
Truncated

Test 27

Group: 4, 5

Verdict: ACCEPTED

input
20000 100
50000000000000 50000000000000 ...

correct output
200
50000000000000 1 201 401 601 8...

user output
200
50000000000000 20000 19999 199...
Truncated

Test 28

Group: 4, 5

Verdict: ACCEPTED

input
181818 11
5500005500000 5500005500000 55...

correct output
181818
500000500000 1 16529 33058 495...

user output
16539
5500005500000 181818 181817 18...
Truncated

Test 29

Group: 4, 5

Verdict: ACCEPTED

input
10000 200
100000000000000 10000000000000...

correct output
50
100000000000000 1 51 101 151 2...

user output
50
100000000000000 10000 9999 999...
Truncated

Test 30

Group: 4, 5

Verdict: ACCEPTED

input
6666 300
150015001500150 15001500150015...

correct output
1111
3000300030003 1 23 45 67 89 11...

user output
33
150015001500150 6666 6665 6664...
Truncated

Test 31

Group: 4, 5

Verdict: ACCEPTED

input
4000 500
250000000000000 25000000000000...

correct output
8
250000000000000 1 9 17 25 33 4...

user output
8
250000000000000 4000 3999 3998...
Truncated

Test 32

Group: 4, 5

Verdict: ACCEPTED

input
2857 700
350017500875000 35001750087500...

correct output
2857
500025001250 1 5 9 13 17 21 25...

user output
26
350017500875000 2857 2856 2855...
Truncated

Test 33

Group: 4, 5

Verdict: ACCEPTED

input
2000 1000
500000000000000 50000000000000...

correct output
2
500000000000000 1 3 5 7 9 11 1...

user output
2
500000000000000 2000 1999 1998...
Truncated

Test 34

Group: 5

Verdict: ACCEPTED

input
23514 2
18103 5348 3625 12835 15660 90...

correct output
23513
6865 1 11793 
11202 1 11794 
36 1 11795 
5348 2 11795 
...

user output
17635
23512 6280 1884 
23510 7660 22648 
23508 11004 2585 
23506 14914 16048 
...
Truncated

Test 35

Group: 5

Verdict: ACCEPTED

input
23514 2
18292 21082 22492 20359 17760 ...

correct output
23514
8265 1 11746 
8926 1 11747 
1101 1 11748 
9890 2 11748 
...

user output
17635
23512 6401 22796 
23510 15829 19205 
23508 14764 19065 
23506 21677 6478 
...
Truncated

Test 36

Group: 5

Verdict: ACCEPTED

input
940 2
73 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

correct output
940
73 1 640 
1 2 640 
1 3 640 
1 4 640 
...

user output
940
288385396 719 181 
84122941 719 226 
43831749 719 640 
40891964 719 501 
...
Truncated

Test 37

Group: 4, 5

Verdict: ACCEPTED

input
2 2
50000000000000 50000000000000

correct output
1
50000000000000 1 2 

user output
1
50000000000000 1 2 

Test 38

Group: 5

Verdict: ACCEPTED

input
100000 5
134 153 148 128 126 146 165 16...

correct output
98678
33 1 20010 40009 59997 80000 
10 1 20010 40010 59997 80000 
3 1 20010 40010 59997 80001 
58 1 20011 40010 59997 80001 
...

user output
20042
200 30828 5309 56413 75067 689...
Truncated

Test 39

Group: 5

Verdict: ACCEPTED

input
100000 5
152 137 163 145 132 157 183 15...

correct output
98711
1 1 19996 40005 60007 80009 
71 1 19996 40005 60008 80009 
46 1 19997 40005 60008 80009 
24 1 19997 40005 60008 80010 
...

user output
20044
199 60605 63696 91012 38184 82...
Truncated

Test 40

Group: 5

Verdict:

input
10 5
1499332 1501242 1498874 150016...

correct output
10
574 1 2 5 7 9 
1498721 1 3 5 7 9 
37 1 3 6 7 9 
116 2 3 6 7 9 
...

user output
-1

Test 41

Group: 5

Verdict:

input
100 50
1002132999440 1001266333597 10...

correct output
100
1267999683 1 2 4 6 8 10 12 14 ...

user output
-1

Test 42

Group: 5

Verdict: ACCEPTED

input
1000 50
100346633179 101226632849 1003...

correct output
1000
1839998687 1 20 40 60 80 100 1...

user output
249
101353299541 543 880 250 441 6...
Truncated

Test 43

Group: 5

Verdict: ACCEPTED

input
1000000 2
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
999996
1 1 707107 
2 2 707107 
3 3 707107 
4 4 707107 
...

user output
750000
999999 1000000 999999 
999997 999998 999997 
999995 999996 999995 
999993 999994 99
...
Truncated

Test 44

Group: 5

Verdict:

input
1000000 2
999999551533 1000000473528 100...

correct output
1000000
146192314 1 500000 
999853359219 1 500001 
146463134 2 500001 
999854010394 2 500002 
...

user output
(empty)

Test 45

Group: 5

Verdict: ACCEPTED

input
666666 3
1500001336447 1500001298201 15...

correct output
666666
1499958849879 1 222223 444445 ...

user output
370370
1500001833332 116528 487981 40...
Truncated

Test 46

Group: 5

Verdict: ACCEPTED

input
400000 5
2499999946636 2500000060399 25...

correct output
400000
2499910300054 1 80001 160001 2...

user output
144000
2500000199995 148576 392209 10...
Truncated

Test 47

Group: 5

Verdict: ACCEPTED

input
2336 856
42808218598 42808218183 428082...

correct output
2336
10257 1 3 6 9 11 14 17 20 22 2...

user output
63
42808219490 879 1997 955 1398 ...
Truncated

Test 48

Group: 5

Verdict: ACCEPTED

input
285714 7
3500003576920 3500003507271 35...

correct output
285714
499997032073 1 40817 81633 122...

user output
285708
3500003642854 240082 233991 15...
Truncated

Test 49

Group: 5

Verdict: ACCEPTED

input
181818 11
5500005515540 5500005459088 55...

correct output
181818
500002072749 1 16529 33058 495...

user output
181764
5500005590904 118480 130508 10...
Truncated

Test 50

Group: 5

Verdict: ACCEPTED

input
40000 50
25000000005730 24999999994976 ...

correct output
40000
4690 1 800 1600 2401 3200 4001...

user output
1584
25000000019950 30890 453 25541...
Truncated

Test 51

Group: 5

Verdict: ACCEPTED

input
20000 100
50000000003586 50000000000483 ...

correct output
19998
3844 1 201 401 600 801 1001 12...

user output
398
50000000009900 5563 2781 2884 ...
Truncated

Test 52

Group: 5

Verdict: ACCEPTED

input
10000 200
100000000000713 99999999996921...

correct output
9995
84 1 51 100 151 201 250 301 35...

user output
137
100000000004800 3131 6034 4334...
Truncated

Test 53

Group: 5

Verdict: ACCEPTED

input
6666 300
150015001497695 15001500150098...

correct output
6666
6771 1 23 45 67 89 112 134 156...

user output
993
150015001503183 861 2102 2478 ...
Truncated

Test 54

Group: 5

Verdict: ACCEPTED

input
4000 500
250000000001078 24999999999820...

correct output
3979
93 1 9 16 24 32 40 48 56 64 72...

user output
32
250000000001500 2830 1919 1773...
Truncated

Test 55

Group: 5

Verdict: ACCEPTED

input
2857 700
350017500876401 35001750087429...

correct output
2857
500024974229 1 5 9 13 17 21 25...

user output
1797
350017500875772 754 752 2128 1...
Truncated

Test 56

Group: 5

Verdict:

input
2000 1000
499999999999833 50000000000035...

correct output
1955
1 1 2 4 6 8 11 13 15 17 19 21 ...

user output
-1