Submission #166412

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
166412	2019-12-02T07:55:22 Z	Sensei	Hokej (COCI17_hokej)	C++17	48 / 120	514 ms	6812 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 = -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

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.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	8 ms	508 KB	Output is correct
3	Correct	29 ms	824 KB	Output is correct
4	Incorrect	2 ms	376 KB	Output isn't correct
5	Correct	11 ms	632 KB	Output is correct
6	Incorrect	5 ms	376 KB	Output isn't correct
7	Incorrect	10 ms	632 KB	Output isn't correct
8	Incorrect	93 ms	2012 KB	Output isn't correct
9	Incorrect	514 ms	6628 KB	Output isn't correct
10	Incorrect	513 ms	6812 KB	Output isn't correct