답안 #191321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
191321	2020-01-14T15:27:21 Z	atoiz	Naan (JOI19_naan)	C++14	24 / 100	15 ms	504 KB

naan

/*input
7 1
1
2
3
4
5
6
7
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

// credit: https://codeforces.com/blog/entry/66022?#comment-500539

struct Frac
{
	uint64_t nume, demo;

	Frac(uint64_t _nume = 0, uint64_t _demo = 1): nume(_nume), demo(_demo) {}

	bool operator<(const Frac fr) const
	{
		if (nume / demo != fr.nume / fr.demo) return nume / demo < fr.nume / fr.demo;
		return (nume - nume / demo * demo) * fr.demo < (fr.nume / fr.demo * fr.demo) * demo;
	}

	bool operator<=(const Frac fr) const
	{
		if (nume / demo != fr.nume / fr.demo) return nume / demo < fr.nume / fr.demo;
		return (nume - nume / demo * demo) * fr.demo <= (fr.nume / fr.demo * fr.demo) * demo;
	}

	Frac operator+(const uint64_t x) const
	{
		return {nume + demo * x, demo};
	}

	Frac operator-(const uint64_t x) const
	{
		return {nume - demo * x, demo};
	}

	Frac operator/ (const uint64_t x) const
	{
		return {nume, demo * x};
	}

	friend ostream& operator<< (ostream &os, const Frac fr)
	{
		return os << fr.nume << ' ' << fr.demo;
	}
};

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	uint32_t N, L;
	cin >> N >> L;
	vector<vector<uint32_t>> V(N, vector<uint32_t>(L));
	for (auto &vec : V) for (auto &i : vec) cin >> i;

	vector<vector<Frac>> joints(N, vector<Frac>(N, {0, 1}));
	for (uint32_t person = 0; person < N; ++person) {
		uint64_t total = accumulate(V[person].begin(), V[person].end(), (uint32_t) 0);

		uint32_t flavor = 0, happiness = 0;
		for (uint32_t split = 1; split < N; ++split) {
			Frac target(total * split, N);

			while (Frac(happiness + V[person][flavor], 1) <= target) {
				happiness += V[person][flavor];
				++flavor;
			}

			joints[person][split] = ((target - happiness) / V[person][flavor]) + flavor;
		}
	}

	vector<uint32_t> P(N);
	vector<bool> used(N, false);
	for (uint32_t joint = 1; joint < N; ++joint) {
		uint32_t candidate = N;
		for (uint32_t person = 0; person < N; ++person) {
			if ((not used[person]) and (candidate == N or joints[person][joint] < joints[candidate][joint])) {
				candidate = person;
			}
		}
		P[joint - 1] = candidate;
		used[candidate] = true;
		cout << joints[candidate][joint] << '\n';
	}

	for (uint32_t person = 0; person < N; ++person) {
		if (not used[person]) {
			P[N - 1] = person;
			break;
		}
	}

	for (auto person : P) {
		cout << person + 1 << ' ';
	}

	return 0;
}

Subtask #1

0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	3 ms	376 KB	Output is correct
5	Correct	3 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	380 KB	Output is correct
8	Incorrect	2 ms	376 KB	Not a fair distribution.
9	Halted	0 ms	0 KB	-

Subtask #2

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	3 ms	348 KB	Output is correct
5	Correct	3 ms	504 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	15 ms	376 KB	Output is correct
9	Correct	3 ms	504 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	3 ms	428 KB	Output is correct
12	Correct	6 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	3 ms	376 KB	Output is correct
15	Correct	3 ms	376 KB	Output is correct
16	Correct	3 ms	376 KB	Output is correct
17	Correct	3 ms	376 KB	Output is correct
18	Correct	3 ms	376 KB	Output is correct
19	Correct	3 ms	376 KB	Output is correct
20	Correct	3 ms	376 KB	Output is correct
21	Correct	3 ms	376 KB	Output is correct
22	Correct	3 ms	376 KB	Output is correct
23	Correct	1 ms	376 KB	Output is correct
24	Correct	3 ms	376 KB	Output is correct
25	Correct	2 ms	376 KB	Output is correct
26	Correct	2 ms	248 KB	Output is correct
27	Correct	3 ms	376 KB	Output is correct

Subtask #3

0 / 71.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	3 ms	376 KB	Output is correct
5	Correct	3 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	380 KB	Output is correct
8	Incorrect	2 ms	376 KB	Not a fair distribution.
9	Halted	0 ms	0 KB	-