Submission #166410

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
166410	2019-12-02T07:46:23 Z	Sensei	Hokej (COCI17_hokej)	C++17	84 / 120	567 ms	6736 KB

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

	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

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:111:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(substitutions.size() <= 3 * N);
         ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~

Subtask #1

84.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Incorrect	8 ms	504 KB	Output isn't correct
3	Incorrect	30 ms	824 KB	Output isn't correct
4	Incorrect	3 ms	256 KB	Output isn't correct
5	Correct	11 ms	632 KB	Output is correct
6	Correct	6 ms	504 KB	Output is correct
7	Correct	10 ms	632 KB	Output is correct
8	Correct	92 ms	2028 KB	Output is correct
9	Correct	567 ms	6664 KB	Output is correct
10	Correct	529 ms	6736 KB	Output is correct