Submission #166412

#	Time	Username	Problem	Language	Result	Execution time	Memory
166412		Sensei	Hokej (COCI17_hokej)	C++17	48 / 120	514 ms	6812 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++) {
		int best_timeline = -1;
		int best_time_on_field = -1;
		int best_time_left = -1;

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

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

			// 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";

	assert(substitutions.size() <= 3 * 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
*/

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from hokej.cpp:1:
hokej.cpp: In function 'int main()':
hokej.cpp:119:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(substitutions.size() <= 3 * N);
         ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~

• Subtask 1: 48 / 120