Submission #138852

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138852	2019-07-30T14:25:21 Z	KCSC	Hokej (COCI17_hokej)	C++14	120 / 120	545 ms	22976 KB

hokej

#include <bits/stdc++.h>
using namespace std;

const int DIM = 500005;

struct Player {
	int x, y, id;
} arr[DIM];

vector<pair<int, int>> chn[DIM];
vector<int> fst;

inline bool cmp(Player p1, Player p2) {
	if (p1.x == p2.x)
		return p1.y < p2.y;
	return p1.x > p2.x;
}

int main(void) {
#ifdef HOME
	freopen("hokej.in", "r", stdin);
	freopen("hokej.out", "w", stdout);
#endif
	int m, n;
	cin >> m >> n;
	for (int i = 1; i <= n; ++i) {
		int x, y;
		cin >> x >> y;
		arr[i] = {x, y, i};
	}
	sort(arr + 1, arr + n + 1, cmp);
	int cnt = 0, t = m;
	long long ans = 0;
	for (int i = 1, b = 0, tp = 0, lst = 0; i <= n and b < 6; ) {
		int s = arr[i].x, e = arr[i].y, id = arr[i].id;
		if (e == 0) {
			++i;
			continue;
		}
		t = min(e, m - tp);
		if (tp == 0 and fst.size() < 6)
			fst.push_back(id);
		else if (b != 5 and e == m) {
			++b; ++i;
			ans += 1LL * m * s;
			fst.push_back(id);
			continue;	// no more updates here
		} else {
			++cnt;
			chn[tp].push_back(make_pair(lst, id));
		}
		tp += t;
		ans += 1LL * t * s;
		arr[i].y -= t; lst = id;
		lst = id;
		if (tp == m) {
			++b;
			tp = 0;
		}
	}
	cout << ans << "\n";
	for (int i = 0; i < 6; ++i)
		cout << fst[i] << " ";
	cout << "\n" << cnt << "\n";
	for (int i = 0; i < m; ++i) {
		reverse(chn[i].begin(), chn[i].end());
		for (int j = 0; j < chn[i].size(); ++j) 
			cout << i << " " << chn[i][j].first << " " << chn[i][j].second << "\n"; 
	}
	return 0;
}

Compilation message

hokej.cpp: In function 'int main()':
hokej.cpp:67:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < chn[i].size(); ++j) 
                   ~~^~~~~~~~~~~~~~~

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	12024 KB	Output is correct
2	Correct	19 ms	12152 KB	Output is correct
3	Correct	42 ms	12664 KB	Output is correct
4	Correct	14 ms	12152 KB	Output is correct
5	Correct	23 ms	12360 KB	Output is correct
6	Correct	16 ms	12152 KB	Output is correct
7	Correct	20 ms	12280 KB	Output is correct
8	Correct	105 ms	14404 KB	Output is correct
9	Correct	532 ms	22940 KB	Output is correct
10	Correct	545 ms	22976 KB	Output is correct