제출 #378548

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378548		Kevin_Zhang_TW	Gift (IZhO18_nicegift)	C++17	100 / 100	1220 ms	218696 KiB

nicegift

#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';
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 51 / 51