Submission #124005

#	Time	Username	Problem	Language	Result	Execution time	Memory
124005		imyujin	Naan (JOI19_naan)	C++14	100 / 100	3098 ms	128284 KiB

naan

#include<stdio.h>
#include<bitset>

using namespace std;

#define MAXN 2005
#define fi first
#define se second
#define llint __int128_t

typedef long long lint;
typedef pair<lint, lint> pll;

lint V[MAXN][MAXN];
lint Vsum[MAXN][MAXN];
pll X[MAXN][MAXN];
bitset<MAXN> chk;
int P[MAXN];

bool cmp(pll a, pll b) {
	return (llint)a.fi * b.se < (llint)a.se * b.fi;
}

lint ggcd(lint a, lint b) {
	if(a % b == 0) return b;
	return ggcd(b, a % b);
}

pll mkfrac(lint a, lint b) {
	lint g = ggcd(a, b);
	return make_pair(a / g, b / g);
}

int main() {
	int N, L;

	scanf("%d%d", &N, &L);
	for(int i = 0; i < N; i++) for(int j = 0; j < L; j++) scanf("%lld", &V[i][j]);

	for(int i = 0; i < N; i++) {
		Vsum[i][0] = V[i][0];
		for(int j = 1; j < L; j++) Vsum[i][j] = Vsum[i][j - 1] + V[i][j];
	}
	for(int i = 0; i < N; i++) for(int j = 1; j < N; j++) {
		int s = 0, e = L - 1;
		while(s < e) {
			int m = (s + e) / 2;
			//printf("i = %d, m = %d, Vsum[i][m] = %lld\n", i, m, Vsum[i][m]);
			if(Vsum[i][m] * N < Vsum[i][L - 1] * j) s = m + 1;
			else e = m;
		}
		pll left = mkfrac(Vsum[i][s] * N - Vsum[i][L - 1] * j, N * V[i][s]);
		X[i][j] = mkfrac((s + 1) * left.se - left.fi, left.se);
		//printf("i = %d, j = %d, s = %d, left = (%lld, %lld), X[i][j] = (%lld, %lld)\n", i, j, s, left.fi, left.se, X[i][j].fi, X[i][j].se);
	}

	for(int i = 1; i < N; i++) {
		int mn = -1;
		for(int j = 0; j < N; j++) if(!chk[j]) {
			if(mn == - 1 || cmp(X[j][i], X[mn][i])) mn = j;
		}
		printf("%lld %lld\n", X[mn][i].fi, X[mn][i].se);
		chk[mn] = true;
		P[i] = mn;
	}
	for(int i = 1; i < N; i++) printf("%d ", P[i] + 1);
	for(int i = 0; i < N; i++) if(!chk[i]) printf("%d", i + 1);

	return 0;
}

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &L);
  ~~~~~^~~~~~~~~~~~~~~~
naan.cpp:38:61: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < N; i++) for(int j = 0; j < L; j++) scanf("%lld", &V[i][j]);
                                                        ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 24 / 24
• Subtask 3: 71 / 71