Submission #164766

#	Time	Username	Problem	Language	Result	Execution time	Memory
164766		maruii	Naan (JOI19_naan)	C++14	0 / 100	3 ms	504 KiB

naan

#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 (stderr)

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
• Subtask 2: 0 / 24
• Subtask 3: 0 / 71