Submission #166409

#	Time	Username	Problem	Language	Result	Execution time	Memory
166409		Sensei	Hokej (COCI17_hokej)	C++17	84 / 120	539 ms	6652 KiB

hokej

#include <bits/stdc++.h>

using namespace std;

class Player {
public:
	int K, L;
	int no;

	Player () {
		K = 0;
		L = 0;
		no = 0;
	}
};

class Timeline {
public:
	int t;
	vector<int> players;

	Timeline () {
		t = 0;
		players.clear();
	}
};

class Substitute {
public:
	int t;
	int no1, no2;

	Substitute () {
		t = 0;
		no1 = 0;
		no2 = 0;
	}
};

Timeline timelines[6];
Player init_players[6];
vector<Substitute> substitutions;

int main () {
	int N, M;

	cin >> M >> N;

	vector<Player> players;

	for (int i = 1; i <= N; i++) {
		Player player;

		cin >> player.K >> player.L;
		player.no = i;

		players.push_back(player);
	}

	sort(players.begin(), players.end(), [](Player a, Player b) {
		if (a.K == b.K) {
			return a.L > b.L;
		}

		return a.K > b.K;
	});

	long long ans = 0;

	for (int i = 0; i < N; i++) {
		// cerr << i << " " << players[i].K << " " << players[i].L << "\n";
		int best_timeline = -1;
		int best_time_on_field = 0;

		for (int t = 0; t < 6; t++) {
			int time_on_field = min(players[i].L, M - timelines[t].t);

			if (time_on_field > best_time_on_field) {
				best_timeline = t;
				best_time_on_field = time_on_field;
			}
		}

		if (best_time_on_field > 0) {
			if (timelines[best_timeline].players.size() == 0) {
				init_players[best_timeline] = players[i];
			}
			else {
				Substitute substitution;
				substitution.t = timelines[best_timeline].t;
				substitution.no1 = timelines[best_timeline].players.back();
				substitution.no2 = players[i].no;

				substitutions.push_back(substitution);
			}

			timelines[best_timeline].players.push_back(players[i].no);

			timelines[best_timeline].t += best_time_on_field;
			ans += players[i].K * 1LL * best_time_on_field;
		}
	}

	cout << ans << "\n";

	for (int t = 0; t < 6; t++) {
		printf("%d%c", init_players[t].no, " \n"[t + 1 == 6]);
	}

	cout << substitutions.size() << "\n";

	sort(substitutions.begin(), substitutions.end(), [](Substitute a, Substitute b) {
		if (a.t == b.t) {
			return a.no1 < b.no1;
		}

		return a.t < b.t;
	});

	for (Substitute &substitution : substitutions) {
		printf("%d %d %d\n", substitution.t, substitution.no1, substitution.no2);
	}

	return 0;
}
/*
200 6
3 ​​200
4 ​​200
5 ​​200
6 ​​200
7 ​​200
8 ​​200
*/

• Subtask 1: 84 / 120