제출 #560565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
560565		blue	Naan (JOI19_naan)	C++17	29 / 100	117 ms	64016 KiB

naan

#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vi = vector<int>;
 
const ll mx = 2'000;
 
int N, L;
 
struct frac
{
	ll n;
	ll d;
};
 
bool operator < (frac A, frac B)
{
	return A.n*B.d < B.n*A.d;
}
 
bool operator == (frac A, frac B)
{
	return A.n*B.d == B.n*A.d;
}
 
bool operator > (frac A, frac B)
{
	return B < A;
}
 
bool operator <= (frac A, frac B)
{
	return A.n*B.d <= B.n*A.d;
}
 
frac operator + (frac A, frac B)
{
	return {A.n*B.d + B.n*A.d, A.d*B.d};
}
 
frac operator - (frac A, frac B)
{
	return {A.n*B.d - B.n*A.d, A.d*B.d};
}
 
frac operator / (frac A, frac B)
{
	return {A.n*B.d, B.n*A.d};
}
 
vvll V(1+mx, vll(1+mx, 0));
 
frac getVpref(int p, frac i)
{
	if(i.n == i.d * L)
		return {V[p][L], 1};
	// return V[p][i.n/i.d] + (V[i.n/i.d + 1] - V[i.n/i.d]) * ((i.n % i.d) / i.d);
 
	return frac{V[p][i.n/i.d]*i.d + (V[p][i.n/i.d + 1] - V[p][i.n/i.d]) * (i.n % i.d), i.d};
}
 
int main()
{
	cin >> N >> L;
 
	for(int i = 1; i <= N; i++)
	{
		for(int j = 1; j <= L; j++)
		{
			cin >> V[i][j];
			V[i][j] += V[i][j-1];
		}
	}
 
	vi visit(1+N, 0);
 
	vector<frac> X;
	vector<int> P;
 
	X.push_back({0, 1});
 
	vector<frac> curr(1+N, frac{0, 1});
 
	int xct = 0;
 

	assert(N <= 6);

	for(int t = 1; t < N; t++)
	{
		// cerr << "\n\n";
		// cerr << "t = " << t << '\n';
		int bestp = -1;
		for(int i = 1; i <= N; i++)
		{
			if(visit[i]) continue;
 
			while(getVpref(i, curr[i]) < getVpref(i, X.back()) + frac{V[i][L], N})
			{
				xct++;
				// if(xct >= 50'000'000)
				// 	assert(0);
				if(curr[i].d == 1)
				{
					if(curr[i].n < L && frac{V[i][curr[i].n + 1], 1} <= getVpref(i, X.back()) + frac{V[i][L], N})
						curr[i].n++;
					else
					{
						frac thisfrac = (getVpref(i, X.back()) + frac{V[i][L], N} - getVpref(i, curr[i])) / frac{V[i][curr[i].n + 1] - V[i][curr[i].n], 1};
						curr[i] = curr[i] + thisfrac;
						break;
					}
				}
				else
				{
					curr[i] = frac{min(curr[i].n / curr[i].d + 1, ll(L)), 1};
					if(getVpref(i, curr[i]) > getVpref(i, X.back()) + frac{V[i][L], N})
						curr[i] = curr[i] - (getVpref(i, curr[i]) - (getVpref(i, X.back()) + frac{V[i][L], N})) / frac{V[i][curr[i].n]  - V[i][curr[i].n - 1], 1};
				}
			}
 
			if(bestp == -1 || curr[bestp] > curr[i])
				bestp = i;
			// cerr << i << " : " << curr[i].n << ' ' << curr[i].d << '\n';
		}
 
		visit[bestp] = 1;
		P.push_back(bestp);
		X.push_back(curr[bestp]);
	}
 
	for(int i = 1; i <= N; i++)
		if(!visit[i])
			P.push_back(i);
 
 
	for(int i = 1; i <= N-1; i++)
		cout << X[i].n << ' ' << X[i].d << '\n';
	for(int p : P)
		cout << p << ' ';
	cout << '\n';
}

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