Submission #123847

#	Time	Username	Problem	Language	Result	Execution time	Memory
123847		khsoo01	Naan (JOI19_naan)	C++11	100 / 100	1028 ms	94748 KiB

naan

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N = 2005;

ll n, m, s[N][N], ans[N];

bool dn[N];

struct frac {
	ll j, m;
	bool operator < (frac &T) {
		if(j / m != T.j / T.m) return j / m < T.j / T.m;
		return (j%m) * T.m < (T.j%T.m) * m;
	}
} x[N][N];

frac get_border (ll I, ll A, ll B) {
	ll S = 0, E = m;
	while(S<E) {
		ll M = (S+E)/2+1;
		s[I][M] * B > A ? E = M-1 : S = M;
	}
	A -= s[I][S] * B;
	frac ret = {A, (s[I][S+1] - s[I][S]) * B};
	return {ret.j + ret.m * S, ret.m};
}

int main()
{
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++) {
		for(ll j=1;j<=m;j++) {
			scanf("%lld",&s[i][j]);
			s[i][j] += s[i][j-1];
		}
		s[i][m+1] = s[i][m] + 1;
		for(ll j=1;j<=n;j++) {
			x[i][j] = get_border(i, j*s[i][m], n);
		}
	}
	for(ll i=1;i<=n;i++) {
		ll I = -1;
		for(ll j=1;j<=n;j++) {
			if(dn[j]) continue;
			if(I == -1 || x[j][i] < x[I][i]) I = j;
		}
		ans[i] = I;
		dn[I] = true;
		if(i != n) printf("%lld %lld\n", x[I][i].j, x[I][i].m);
	}
	for(ll i=1;i<=n;i++) {
		printf("%lld ", ans[i]);
	}
}

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~
naan.cpp:35:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld",&s[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~

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