oj.uz

Submission #191319

# Submission time Handle Problem Language Result Execution time Memory
191319 2020-01-14T15:19:29 Z atoiz Naan (JOI19_naan) C++14
29 / 100
 37 ms 7964 KB 
/*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
	{
		return nume * fr.demo < fr.nume * demo;
	}

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

	bool operator==(const Frac fr) const
	{
		return nume * fr.demo == fr.nume * 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) {
		uint32_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
5.0 / 5.0

# Verdict Execution time Memory 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 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 0 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 504 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 248 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 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 504 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 0 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 7 ms 376 KB Output is correct
23 Correct 3 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 3 ms 376 KB Output is correct
27 Correct 3 ms 376 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory 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 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 0 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 3 ms 504 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 3 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 248 KB Output is correct
23 Correct 3 ms 376 KB Output is correct
24 Correct 3 ms 376 KB Output is correct
25 Correct 3 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 3 ms 376 KB Output is correct
29 Correct 2 ms 376 KB Output is correct
30 Correct 3 ms 376 KB Output is correct
31 Correct 3 ms 376 KB Output is correct
32 Correct 3 ms 376 KB Output is correct
33 Correct 3 ms 504 KB Output is correct
34 Correct 3 ms 376 KB Output is correct
35 Correct 0 ms 376 KB Output is correct
36 Correct 2 ms 376 KB Output is correct
37 Correct 7 ms 376 KB Output is correct
38 Correct 3 ms 376 KB Output is correct
39 Correct 3 ms 376 KB Output is correct
40 Correct 2 ms 376 KB Output is correct
41 Correct 3 ms 376 KB Output is correct
42 Correct 3 ms 376 KB Output is correct
43 Incorrect 37 ms 7964 KB X_i is not increasing
44 Halted 0 ms 0 KB -