Submission #170731

#	Time	Username	Problem	Language	Result	Execution time	Memory
170731		arnold518	Naan (JOI19_naan)	C++14	100 / 100	1955 ms	116868 KiB

naan

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;
const ll INF = numeric_limits<ll>::max();

struct Frac
{
	ll x, y;
	Frac() {}
	Frac(ll x, ll y) : x(x), y(y) {}
	void norm()
	{
		ll g=__gcd(x, y);
		x/=g; y/=g;
	}
};

bool operator < (const Frac &p, const Frac &q)
{
	return (__int128)p.y*q.x<(__int128)q.y*p.x;
}

int N, L;
ll A[MAXN+10][MAXN+10];
Frac B[MAXN+10][MAXN+10];
bool vis[MAXN+10];
int ans[MAXN+10];

int main()
{
	int i, j;
	scanf("%d%d", &N, &L);
	
	for(i=1; i<=N; i++)
	{
		ll S=0;
		for(j=1; j<=L; j++) scanf("%lld", &A[i][j]), S+=A[i][j];
		for(j=1; j<=L; j++) A[i][j]*=N;

		for(j=1; j<=L; j++) A[i][j]+=A[i][j-1];

		for(j=1; j<N; j++)
		{
			ll now=j*S;
			int pos=upper_bound(A[i], A[i]+L+1, now)-A[i];
			now-=A[i][pos-1];

			Frac t;
			t.x=(A[i][pos]-A[i][pos-1]);
			t.y=now+(A[i][pos]-A[i][pos-1])*(pos-1);

			t.norm();
			B[i][j]=t;
		}
	}

	for(i=1; i<N; i++)
	{
		pair<Frac, int> val;
		val.first={1, INF};
		val.second=-1;

		for(j=1; j<=N; j++)
		{
			if(vis[j]) continue;
			pair<Frac, int> now;
			now.first=B[j][i];
			now.second=j;
			val=min(val, now);
		}

		ans[i]=val.second;
		vis[val.second]=true;
		printf("%lld %lld\n", val.first.y, val.first.x);
	}
	for(i=1; i<=N; i++) if(!vis[i]) ans[N]=i;

	for(i=1; i<=N; i++) printf("%d ", ans[i]);
}

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:42:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(j=1; j<=L; j++) scanf("%lld", &A[i][j]), S+=A[i][j];
                       ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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