Submission #535204

#	Time	Username	Problem	Language	Result	Execution time	Memory
535204		pooyashams	Naan (JOI19_naan)	C++17	100 / 100	782 ms	131832 KiB

naan

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <cassert>

using namespace std;
typedef long long ll;
#define int ll
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 2012;

struct mfint
{
	ll a, b; // a/b
	mfint()
	{
		a = 1;
		b = 1;
	};
	mfint(ll _a, ll _b)
	{
		a = _a;
		b = _b;
		ll x = gcd(a, b);
		a /= x;
		b /= x;
	}
	inline bool operator<(const mfint &o) const
	{
		return 1.0l*a*o.b < 1.0l*o.a*b;
	}
};

int vals[maxn][maxn];
int ps[maxn][maxn];
mfint blues[maxn][maxn];
int f;

ll n, L;

inline void prn(mfint a)
{
	cerr << a.a << "/" << a.b << " ";
}

//inline int cmp(int i, int j)
//{
//	return blues[i][f] < blues[j][f];
//}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> L;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < L; j++)
		{
			cin >> vals[i][j];
			ps[i][j+1] = ps[i][j]+vals[i][j];
		}
	}
	for(int i = 0; i < n; i++)
	{
		int p = 0;
		ll s = ps[i][L];
		for(int j = 1; j <= n; j++)
		{
			while( (n*(ps[i][p] + vals[i][p])) < s*j )
				p++;
			blues[i][j-1] = mfint(s*j-n*ps[i][p] + n*vals[i][p]*p, n*vals[i][p]);
			//prn(blues[i][j]);
		}
	}
	vector<int> rem(n);
	iota(rem.begin(), rem.end(), 0);
	vector<int> prm;
	vector<mfint> mfs;
	for(int f = 0; f < n; f++)
	{
		int mnidx = min_element(rem.begin(), rem.end(), [&](int i, int j){ return blues[i][f] < blues[j][f];}) - rem.begin();
		//cerr << rem[mnidx] << endl;
		prm.push_back(rem[mnidx]);
		mfs.push_back(blues[rem[mnidx]][f]);
		rem.erase(rem.begin()+mnidx);
	}
	mfs.pop_back();
	for(mfint m: mfs)
		cout << m.a << " " << m.b << endl;
	for(int x: prm)
		cout << x+1 <<  " ";
	cout << endl;
	return 0;
}

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