CSES - IZhO 2018, day 1

CSES - IZhO 2018, day 1 - Results

Submission details
Task:	Gift
Sender:	Olli
Submission time:	2019-02-16 16:08:44 +0200
Language:	C++
Status:	READY
Result:	49

Feedback
group	verdict	score
#1	ACCEPTED	7
#2	ACCEPTED	11
#3	ACCEPTED	12
#4	ACCEPTED	19
#5	TIME LIMIT EXCEEDED	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.06 s	1, 2, 3, 5	details
#2	ACCEPTED	0.05 s	1, 2, 3, 5	details
#3	ACCEPTED	0.05 s	1, 2, 3, 5	details
#4	ACCEPTED	0.05 s	1, 2, 3, 5	details
#5	ACCEPTED	0.06 s	1, 2, 3, 5	details
#6	ACCEPTED	0.06 s	1, 2, 3, 5	details
#7	ACCEPTED	0.04 s	1, 2, 3, 5	details
#8	ACCEPTED	0.05 s	2, 3, 5	details
#9	ACCEPTED	0.05 s	2, 3, 5	details
#10	ACCEPTED	0.05 s	2, 3, 5	details
#11	ACCEPTED	0.11 s	2, 3, 5	details
#12	ACCEPTED	0.10 s	2, 3, 5	details
#13	ACCEPTED	0.06 s	2, 3, 5	details
#14	ACCEPTED	0.06 s	2, 3, 5	details
#15	ACCEPTED	0.04 s	2, 3, 5	details
#16	ACCEPTED	0.05 s	2, 3, 5	details
#17	ACCEPTED	0.05 s	3, 5	details
#18	ACCEPTED	0.05 s	3, 5	details
#19	ACCEPTED	0.05 s	3, 5	details
#20	ACCEPTED	0.05 s	3, 5	details
#21	ACCEPTED	0.04 s	3, 5	details
#22	ACCEPTED	0.05 s	3, 5	details
#23	ACCEPTED	1.89 s	4, 5	details
#24	ACCEPTED	1.15 s	4, 5	details
#25	ACCEPTED	0.66 s	4, 5	details
#26	ACCEPTED	0.52 s	4, 5	details
#27	ACCEPTED	0.07 s	4, 5	details
#28	ACCEPTED	0.33 s	4, 5	details
#29	ACCEPTED	0.07 s	4, 5	details
#30	ACCEPTED	0.06 s	4, 5	details
#31	ACCEPTED	0.06 s	4, 5	details
#32	ACCEPTED	0.07 s	4, 5	details
#33	ACCEPTED	0.06 s	4, 5	details
#34	ACCEPTED	0.09 s	5	details
#35	ACCEPTED	0.09 s	5	details
#36	ACCEPTED	0.06 s	5	details
#37	ACCEPTED	0.05 s	4, 5	details
#38	ACCEPTED	0.18 s	5	details
#39	ACCEPTED	0.17 s	5	details
#40	ACCEPTED	0.06 s	5	details
#41	ACCEPTED	0.05 s	5	details
#42	ACCEPTED	0.06 s	5	details
#43	ACCEPTED	1.86 s	5	details
#44	TIME LIMIT EXCEEDED	--	5	details
#45	TIME LIMIT EXCEEDED	--	5	details
#46	ACCEPTED	1.28 s	5	details
#47	ACCEPTED	0.07 s	5	details
#48	ACCEPTED	1.30 s	5	details
#49	ACCEPTED	1.00 s	5	details
#50	ACCEPTED	0.14 s	5	details
#51	ACCEPTED	0.10 s	5	details
#52	ACCEPTED	0.08 s	5	details
#53	ACCEPTED	0.15 s	5	details
#54	ACCEPTED	0.06 s	5	details
#55	ACCEPTED	0.41 s	5	details
#56	ACCEPTED	0.07 s	5	details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:93:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i = 0; i < ne.size(); ++i) {
              ~~^~~~~~~~~~~
input/code.cpp:102: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() {
	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;
	}

	int c = 1;
	while(sum > 0) {
		ll k1th;
		set<pll>::iterator it = s.end();
		--it;
		int i = n;
		while(i != n - k) {
			--it;
			--i;
		}
		k1th = (*it).first;
		++it;
	//	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(i = n; i > n-k; --i) {
			--it;
			ne.push_back({(*it).first - x, (*it).second});
			mov[c].push_back((*it).second);
		}

		for(i = n; i > n-k; --i) {
			it = s.end();
			--it;
			s.erase(it);	
		}
		for(i = 0; i < ne.size(); ++i) {
			s.insert(ne[i]);
		}
		sum -= x*k;
		++c;
	}

	cout << c-1 << "\n";
	for(int i = 1; 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` view save

correct output
`3 2 3 1 1 3 2 2 2 4` view save

user output
`2 3 3 2 2 4 1` view save

Test 2

Group: 1, 2, 3, 5

Verdict: ACCEPTED

input
`3 2 2 1 1` view save

correct output
`2 1 1 2 1 1 3` view save

user output
`2 1 1 3 1 2 1` view save

Test 3

Group: 1, 2, 3, 5

Verdict: ACCEPTED

input
`3 2 1 2 4` view save

correct output
`-1` view save

user output
`-1` view save

Test 4

Group: 1, 2, 3, 5

Verdict: ACCEPTED

input
`4 2 1 2 3 4` view save

correct output
`3 1 1 3 2 2 4 2 3 4` view save

user output
`3 3 4 3 1 2 4 1 2 1` view save

Test 5

Group: 1, 2, 3, 5

Verdict: ACCEPTED

input
`4 2 1 2 1 5` view save

correct output
`-1` view save

user output
`-1` view save

Test 6

Group: 1, 2, 3, 5

Verdict: ACCEPTED

input
`2 2 4 5` view save

correct output
`-1` view save

user output
`-1` view save

Test 7

Group: 1, 2, 3, 5

Verdict: ACCEPTED

input
`5 2 2 1 3 1 1` view save

correct output
`3 2 1 3 1 2 4 1 3 5` view save

user output
`3 2 3 1 1 5 4 1 3 2` view save

Test 8

Group: 2, 3, 5

Verdict: ACCEPTED

input
`8 2 1 1 9101 17 161 57013 7 567` view save

correct output
`-1` view save

user output
`-1` view save

Test 9

Group: 2, 3, 5

Verdict: ACCEPTED

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

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

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...` view save

correct output
`11 1 1 5 2586 2 5 1 2 6 1 2 7 ...` view save

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 ...` view save

correct output
`42250 1 1 33212 1 2 33212 1 3 33212 1 4 33212 ...` view save

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 ...` view save

correct output
`40020 1 1 27450 1 2 27450 1 3 27450 1 4 27450 ...` view save

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...` view save

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

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...` view save

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

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...` view save

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

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 ...` view save

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

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 ...` view save

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

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 ...` view save

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

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...` view save

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

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...` view save

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

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...` view save

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

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 ...` view save

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

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...` view save

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

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...` view save

correct output
`222222 1500001500001 1 222223 444445 ...` view save

user output
`222222 1500001500001 666666 666665 66...` Truncated

Test 25

Group: 4, 5

Verdict: ACCEPTED

input
`400000 5 2500000000000 2500000000000 25...` view save

correct output
`80000 2500000000000 1 80001 160001 2...` view save

user output
`80000 2500000000000 400000 399999 39...` Truncated

Test 26

Group: 4, 5

Verdict: ACCEPTED

input
`285714 7 3500003500000 3500003500000 35...` view save

correct output
`285714 500000500000 1 40817 81633 122...` view save

user output
`40821 3500003500000 285714 285713 28...` Truncated

Test 27

Group: 4, 5

Verdict: ACCEPTED

input
`20000 100 50000000000000 50000000000000 ...` view save

correct output
`200 50000000000000 1 201 401 601 8...` view save

user output
`200 50000000000000 20000 19999 199...` Truncated

Test 28

Group: 4, 5

Verdict: ACCEPTED

input
`181818 11 5500005500000 5500005500000 55...` view save

correct output
`181818 500000500000 1 16529 33058 495...` view save

user output
`16539 5500005500000 181818 181817 18...` Truncated

Test 29

Group: 4, 5

Verdict: ACCEPTED

input
`10000 200 100000000000000 10000000000000...` view save

correct output
`50 100000000000000 1 51 101 151 2...` view save

user output
`50 100000000000000 10000 9999 999...` Truncated

Test 30

Group: 4, 5

Verdict: ACCEPTED

input
`6666 300 150015001500150 15001500150015...` view save

correct output
`1111 3000300030003 1 23 45 67 89 11...` view save

user output
`33 150015001500150 6666 6665 6664...` Truncated

Test 31

Group: 4, 5

Verdict: ACCEPTED

input
`4000 500 250000000000000 25000000000000...` view save

correct output
`8 250000000000000 1 9 17 25 33 4...` view save

user output
`8 250000000000000 4000 3999 3998...` Truncated

Test 32

Group: 4, 5

Verdict: ACCEPTED

input
`2857 700 350017500875000 35001750087500...` view save

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

user output
`26 350017500875000 2857 2856 2855...` Truncated

Test 33

Group: 4, 5

Verdict: ACCEPTED

input
`2000 1000 500000000000000 50000000000000...` view save

correct output
`2 500000000000000 1 3 5 7 9 11 1...` view save

user output
`2 500000000000000 2000 1999 1998...` Truncated

Test 34

Group: 5

Verdict: ACCEPTED

input
`23514 2 18103 5348 3625 12835 15660 90...` view save

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

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 ...` view save

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

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...` view save

correct output
`940 73 1 640 1 2 640 1 3 640 1 4 640 ...` view save

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` view save

correct output
`1 50000000000000 1 2` view save

user output
`1 50000000000000 1 2` view save

Test 38

Group: 5

Verdict: ACCEPTED

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

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 ...` view save

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...` view save

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 ...` view save

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

Test 40

Group: 5

Verdict: ACCEPTED

input
`10 5 1499332 1501242 1498874 150016...` view save

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 ...` view save

user output
`10 1500135 7 2 9 4 6 1498301 10 5 1 3 8 991 7 10 5 2 1 274 7 3 10 5 9 ...` Truncated

Test 41

Group: 5

Verdict: ACCEPTED

input
`100 50 1002132999440 1001266333597 10...` view save

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

user output
`29 999807000103 35 32 73 89 34 52...` Truncated

Test 42

Group: 5

Verdict: ACCEPTED

input
`1000 50 100346633179 101226632849 1003...` view save

correct output
`1000 1839998687 1 20 40 60 80 100 1...` view save

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 ...` view save

correct output
`999996 1 1 707107 2 2 707107 3 3 707107 4 4 707107 ...` view save

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

Test 44

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`1000000 2 999999551533 1000000473528 100...` view save

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

user output
(empty)

Test 45

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`666666 3 1500001336447 1500001298201 15...` view save

correct output
`666666 1499958849879 1 222223 444445 ...` view save

user output
(empty)

Test 46

Group: 5

Verdict: ACCEPTED

input
`400000 5 2499999946636 2500000060399 25...` view save

correct output
`400000 2499910300054 1 80001 160001 2...` view save

user output
`144000 2500000199995 148576 392209 10...` Truncated

Test 47

Group: 5

Verdict: ACCEPTED

input
`2336 856 42808218598 42808218183 428082...` view save

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

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

Test 48

Group: 5

Verdict: ACCEPTED

input
`285714 7 3500003576920 3500003507271 35...` view save

correct output
`285714 499997032073 1 40817 81633 122...` view save

user output
`285708 3500003642854 240082 233991 15...` Truncated

Test 49

Group: 5

Verdict: ACCEPTED

input
`181818 11 5500005515540 5500005459088 55...` view save

correct output
`181818 500002072749 1 16529 33058 495...` view save

user output
`181764 5500005590904 118480 130508 10...` Truncated

Test 50

Group: 5

Verdict: ACCEPTED

input
`40000 50 25000000005730 24999999994976 ...` view save

correct output
`40000 4690 1 800 1600 2401 3200 4001...` view save

user output
`1584 25000000019950 30890 453 25541...` Truncated

Test 51

Group: 5

Verdict: ACCEPTED

input
`20000 100 50000000003586 50000000000483 ...` view save

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

user output
`398 50000000009900 5563 2781 2884 ...` Truncated

Test 52

Group: 5

Verdict: ACCEPTED

input
`10000 200 100000000000713 99999999996921...` view save

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

user output
`137 100000000004800 3131 6034 4334...` Truncated

Test 53

Group: 5

Verdict: ACCEPTED

input
`6666 300 150015001497695 15001500150098...` view save

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

user output
`993 150015001503183 861 2102 2478 ...` Truncated

Test 54

Group: 5

Verdict: ACCEPTED

input
`4000 500 250000000001078 24999999999820...` view save

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

user output
`32 250000000001500 2830 1919 1773...` Truncated

Test 55

Group: 5

Verdict: ACCEPTED

input
`2857 700 350017500876401 35001750087429...` view save

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

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

Test 56

Group: 5

Verdict: ACCEPTED

input
`2000 1000 499999999999833 50000000000035...` view save

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

user output
`12 500000000000000 1880 1070 564 ...` Truncated

IZhO 2018, day 1

Gift

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Test 44

Test 45

Test 46

Test 47

Test 48

Test 49

Test 50

Test 51

Test 52

Test 53

Test 54

Test 55

Test 56

Tasks

Submissions (Olli)