oj.uz

Submission #378548

# Submission time Handle Problem Language Result Execution time Memory
378548 2021-03-17T01:41:46 Z Kevin_Zhang_TW Gift (IZhO18_nicegift) C++17
100 / 100
 1220 ms 218696 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 1000010;

int n, k;
ll a[MAX_N];

void fail() { puts("-1"), exit(0); }

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k;
	for (int i = 0;i < n;++i)
		cin >> a[i];

	ll sum = accumulate(a, a+n, 0ll), y = sum / k;

	if (sum % k) fail();

	if (*max_element(a, a+n) > y) fail();

	map<ll, vector<int>> sweep;

	// [l, r)
	auto addin = [&](int index, ll l, ll r) {
		sweep[l].pb(index), sweep[r].pb(index);
	};

	DE(y);
	{
		ll v = 0;
		for (int i = 0;i < n;++i) {
			ll l = v, r = l + a[i];
			DE(i, l, r);
			if (r >= y) {
				addin(i, l, y);
				addin(i, 0, r-=y);
			}
			else {
				addin(i, l, r);
			}
			v = r;
		}
	}

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

	{
		ll lstc = 0;
		set<int> cur;
		for (auto [c, vec] : sweep) {
			ll wid = c - lstc; lstc = c;

			if (wid) {
				res.pb(wid, vector<int>(AI(cur)));
				assert(cur.size() == k);
			}

			DE(c), debug(AI(cur));

			for (int ind : vec) {
				if (cur.count(ind)) cur.erase(ind);
				else cur.insert(ind);
			}

			if (c == y) {
				assert(cur.empty());
				break;
			}
		}
	}

	cout << res.size() << '\n';
	for (auto [X, vec] : res) {
		cout << X;
		for (int ind : vec) cout << ' ' << ind+1;
		cout << '\n';
	}
}

Compilation message

nicegift.cpp: In function 'int32_t main()':
nicegift.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
nicegift.cpp:44:2: note: in expansion of macro 'DE'
   44 |  DE(y);
      |  ^~
nicegift.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
nicegift.cpp:49:4: note: in expansion of macro 'DE'
   49 |    DE(i, l, r);
      |    ^~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from nicegift.cpp:1:
nicegift.cpp:71:23: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |     assert(cur.size() == k);
      |            ~~~~~~~~~~~^~~~
nicegift.cpp:14:17: warning: left operand of comma operator has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
nicegift.cpp:74:4: note: in expansion of macro 'DE'
   74 |    DE(c), debug(AI(cur));
      |    ^~
nicegift.cpp:74:25: warning: right operand of comma operator has no effect [-Wunused-value]
   74 |    DE(c), debug(AI(cur));
      |                         ^

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 364 KB n=3
4 Correct 1 ms 364 KB n=4
5 Correct 1 ms 364 KB n=4
6 Correct 2 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 364 KB n=3
4 Correct 1 ms 364 KB n=4
5 Correct 1 ms 364 KB n=4
6 Correct 2 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 48 ms 8672 KB n=50000
12 Correct 45 ms 8292 KB n=50000
13 Correct 1 ms 364 KB n=10
14 Correct 2 ms 492 KB n=685
15 Correct 1 ms 492 KB n=623
16 Correct 2 ms 492 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 364 KB n=3
4 Correct 1 ms 364 KB n=4
5 Correct 1 ms 364 KB n=4
6 Correct 2 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 48 ms 8672 KB n=50000
12 Correct 45 ms 8292 KB n=50000
13 Correct 1 ms 364 KB n=10
14 Correct 2 ms 492 KB n=685
15 Correct 1 ms 492 KB n=623
16 Correct 2 ms 492 KB n=973
17 Correct 2 ms 492 KB n=989
18 Correct 2 ms 492 KB n=563
19 Correct 3 ms 528 KB n=592
20 Correct 4 ms 620 KB n=938
21 Correct 2 ms 492 KB n=747
22 Correct 4 ms 620 KB n=991

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 920 ms 110228 KB n=1000000
2 Correct 563 ms 57164 KB n=666666
3 Correct 277 ms 27116 KB n=400000
4 Correct 491 ms 75316 KB n=285714
5 Correct 10 ms 1260 KB n=20000
6 Correct 398 ms 56512 KB n=181818
7 Correct 6 ms 876 KB n=10000
8 Correct 40 ms 3692 KB n=6666
9 Correct 3 ms 620 KB n=4000
10 Correct 243 ms 18156 KB n=2857
11 Correct 2 ms 620 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 364 KB n=3
4 Correct 1 ms 364 KB n=4
5 Correct 1 ms 364 KB n=4
6 Correct 2 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 48 ms 8672 KB n=50000
12 Correct 45 ms 8292 KB n=50000
13 Correct 1 ms 364 KB n=10
14 Correct 2 ms 492 KB n=685
15 Correct 1 ms 492 KB n=623
16 Correct 2 ms 492 KB n=973
17 Correct 2 ms 492 KB n=989
18 Correct 2 ms 492 KB n=563
19 Correct 3 ms 528 KB n=592
20 Correct 4 ms 620 KB n=938
21 Correct 2 ms 492 KB n=747
22 Correct 4 ms 620 KB n=991
23 Correct 920 ms 110228 KB n=1000000
24 Correct 563 ms 57164 KB n=666666
25 Correct 277 ms 27116 KB n=400000
26 Correct 491 ms 75316 KB n=285714
27 Correct 10 ms 1260 KB n=20000
28 Correct 398 ms 56512 KB n=181818
29 Correct 6 ms 876 KB n=10000
30 Correct 40 ms 3692 KB n=6666
31 Correct 3 ms 620 KB n=4000
32 Correct 243 ms 18156 KB n=2857
33 Correct 2 ms 620 KB n=2000
34 Correct 25 ms 5088 KB n=23514
35 Correct 24 ms 5088 KB n=23514
36 Correct 2 ms 492 KB n=940
37 Correct 1 ms 364 KB n=2
38 Correct 139 ms 21848 KB n=100000
39 Correct 133 ms 21848 KB n=100000
40 Correct 1 ms 364 KB n=10
41 Correct 1 ms 364 KB n=100
42 Correct 10 ms 876 KB n=1000
43 Correct 1187 ms 207948 KB n=1000000
44 Correct 1220 ms 218696 KB n=1000000
45 Correct 851 ms 150416 KB n=666666
46 Correct 612 ms 95284 KB n=400000
47 Correct 217 ms 17772 KB n=2336
48 Correct 502 ms 77244 KB n=285714
49 Correct 433 ms 56564 KB n=181818
50 Correct 256 ms 26716 KB n=40000
51 Correct 231 ms 22752 KB n=20000
52 Correct 216 ms 19812 KB n=10000
53 Correct 208 ms 19176 KB n=6666
54 Correct 214 ms 18284 KB n=4000
55 Correct 206 ms 18028 KB n=2857
56 Correct 204 ms 17132 KB n=2000