제출 #533385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533385		pooyashams	Naan (JOI19_naan)	C++14	29 / 100	659 ms	130512 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 __int128 ll;
typedef long double ld;
typedef pair<int, int> pii;

const ll inf = 1e18;

struct mfint
{
	ll a, b; // a/b
	mfint()
	{
		a = 1;
		b = 1;
	}
	mfint(ll _a)
	{
		a = _a;
		b = 1;
	}
	mfint(ll _a, ll _b)
	{
		a = _a;
		b = _b;
	}
	inline void simp()
	{
		ll x = __gcd(a, b);
		a /= x;
		b /= x;
	}
	inline ll floor()
	{
		return a/b;
	}
	inline ll ceil()
	{
		return (a+b-1)/b;
	}
	inline mfint operator+(mfint y)
	{
		mfint x;
		x.b = b*y.b;
		x.a = a*y.b + b*y.a;
		x.simp();
		return x;
	}
	inline mfint operator-(mfint y)
	{
		mfint x;
		x.b = b*y.b;
		x.a = a*y.b - b*y.a;
		x.simp();
		return x;
	}
	inline mfint operator*(mfint y)
	{
		mfint x;
		x.a = a*y.a;
		x.b = b*y.b;
		x.simp();
		return x;
	}
	inline mfint operator/(mfint y)
	{
		mfint x;
		x.a = a*y.b;
		x.b = b*y.a;
		x.simp();
		return x;
	}
	inline bool operator<(mfint y)
	{
		return a*y.b < b*y.a;
	}
	inline bool operator<=(mfint y)
	{
		return a*y.b <= b*y.a;
	}
	inline bool operator>(mfint y)
	{
		return a*y.b > b*y.a;
	}
	inline bool operator>=(mfint y)
	{
		return a*y.b >= b*y.a;
	}
	inline bool operator==(mfint y)
	{
		return a*y.b == b*y.a;
	}
};

const int maxn = 2012;

int vals[maxn][maxn];
mfint vmf[maxn][maxn];
mfint avgs[maxn];

int n, L;

inline mfint nxtf(int i, mfint f)
{
	mfint a = avgs[i];
	int xv = f.floor();
	mfint x = mfint(xv);
	mfint res;
	res = vmf[i][xv] * (res-f+x);
	if(res >= a)
		return f+(a/vmf[i][xv]);
	a = a-res;
	xv++;
	while(xv < L)
	{
		if(vmf[i][xv] >= a)
			return mfint(xv) + (a/vmf[i][xv]);
		else
			a = a-vmf[i][xv];
		xv++;
	}
	return mfint(-1);
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> L;
	for(int i = 0; i < n; i++)
	{
		int s = 0;
		for(int j = 0; j < L; j++)
		{
			cin >> vals[i][j];
			vmf[i][j] = mfint(vals[i][j]);
			s += vals[i][j];
		}
		avgs[i] = mfint(s, n);
	}
	vector<mfint> divs;
	vector<int> prm;
	vector<int> rems(n);
	iota(rems.begin(), rems.end(), 0);
	mfint lf(0);
	for(int i = 0; i < n; i++)
	{
		mfint bst = nxtf(rems[0], lf);
		int bid = rems[0];
		for(int j: rems)
		{
			mfint enf = nxtf(j, lf);
			if(enf <= bst)
			{
				bst = enf;
				bid = j;
			}
		}
		lf = bst;
		divs.push_back(bst);
		prm.push_back(bid);
		rems.erase(find(rems.begin(), rems.end(), bid));
	}
	divs.pop_back();
	for(auto x: divs)
		cout << (long long)(x.a) << " " << (long long)(x.b) << endl;
	for(int i: prm)
		cout << i+1 << " ";
	cout << endl;
	return 0;
}

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