oj.uz

Submission #164766

# Submission time Handle Problem Language Result Execution time Memory
164766 2019-11-23T09:26:26 Z maruii Naan (JOI19_naan) C++14
0 / 100
 3 ms 504 KB 
#include <bits/stdc++.h>
using namespace std;

int N, L;
int P[10], V[10][10], S[10];
long long A[10], B[10];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N >> L;
	if (N > 6) assert(0);
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= L; ++j)
			cin >> V[i][j];
		S[i] = accumulate(V[i], V[i] + L + 1, 0);
	}

	iota(P, P + N + 1, 0);

	
	B[0] = 1;
	do {

		bool flag = 1;

		for (int i = 1; i <= N; ++i) {
			int x = P[i];
			int t = (A[i - 1] + B[i - 1] - 1) / B[i - 1];
			long long sum = (t * B[i - 1] - A[i - 1]) * V[x][t];
			if (N * sum >= B[i - 1] * S[x]) {
				A[i] = A[i - 1] * N * V[x][t] + B[i - 1] * S[x];
				B[i] = B[i - 1] * N * V[x][t];
				long long g = __gcd(A[i], B[i]);
				A[i] /= g;
				B[i] /= g;
				continue;
			}
			t++;
			while (t <= L) {
				sum += V[x][t] * B[i - 1];
				if (N * sum >= B[i - 1] * S[x]) break;
				t++;
			}
			if (t > L) {
				flag = 0;
				break;
			}
			B[i] = V[x][t] * N * B[i - 1];
			A[i] = B[i] * t - (N * sum - B[i - 1] * S[x]);
			long long g = __gcd(A[i], B[i]);
			A[i] /= g;
			B[i] /= g;
		}
		if (flag) break;
	} while(next_permutation(P + 1, P + N + 1));

	for (int i = 1; i < N; ++i) printf("%d %d\n", A[i], B[i]);
	for (int i = 1; i <= N; ++i) printf("%d ",P[i]);
	return 0;
}

Compilation message

naan.cpp: In function 'int main()':
naan.cpp:57:58: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  for (int i = 1; i < N; ++i) printf("%d %d\n", A[i], B[i]);
                                                ~~~~      ^
naan.cpp:57:58: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 296 KB Not a fair distribution.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -