Submission #445167

#	Time	Username	Problem	Language	Result	Execution time	Memory
445167		Jasiekstrz	Naan (JOI19_naan)	C++17	29 / 100	212 ms	38184 KiB

naan

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e3;
struct Quo
{
	long long x,y;
	Quo(long long _x=0,long long _y=1) : x(_x),y(_y) {};
	//void norm()
	//{
	//	long long c=gcd(x,y);
	//	x/=c;
	//	y/=c;
	//	return;
	//}
};
Quo operator+(Quo a,Quo b)
{
	//long long c=lcm(a.y,b.y);
	//return Quo(a.x*(c/a.y)+b.x*(c/b.y),c);
	return Quo(a.x*b.y+b.x*a.y,a.y*b.y);
}
Quo operator-(Quo a,Quo b)
{
	b.x=-b.x;
	return a+b;
}
Quo operator*(Quo a,Quo b)
{
	return Quo(a.x*b.x,a.y*b.y);
}
bool operator<(Quo a,Quo b)
{
	return a.x*b.y<b.x*a.y;
}
long long tab[N+10][N+10];
long long pref[N+10][N+10];
int it[N+10];
bool vis[N+10];
Quo ans[N+10];
int per[N+10];
Quo read(int i,Quo c)
{
	return Quo(pref[i][c.x/c.y],1)+Quo(tab[i][c.x/c.y+1]*(c.x%c.y),c.y);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,l;
	cin>>n>>l;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=l;j++)
		{
			cin>>tab[i][j];
			pref[i][j]=pref[i][j-1]+tab[i][j];
		}
	}
	ans[0]=Quo(0,1);
	for(int k=1;k<=n;k++)
	{
		Quo bst=Quo(l+1,1);
		int g=0;
		for(int i=1;i<=n;i++)
		{
			if(vis[i])
				continue;
			while(read(i,Quo(it[i]+1,1))<Quo(pref[i][l]*k,n))
				it[i]++;
			//Quo xd=read(i,Quo(it[i],1));
			//xd.norm();
			Quo tmp=Quo(it[i],1)+(Quo(pref[i][l]*k,n)-Quo(pref[i][it[i]],1))*Quo(1,tab[i][it[i]+1]);
			//cerr<<(Quo(pref[i][l],n)-xd).x<<" "<<(Quo(pref[i][l],n)-xd).y<<"\n";
			if(tmp<bst)
			{
				bst=tmp;
				g=i;
			}
		}
		//cerr<<g<<" "<<bst.x<<" "<<bst.y<<"\n";
		ans[k]=bst;
		per[k]=g;
		vis[g]=true;
	}
	for(int i=1;i<n;i++)
	{
		//ans[i].norm();
		cout<<ans[i].x<<" "<<ans[i].y<<"\n";
	}
	for(int i=1;i<=n;i++)
		cout<<per[i]<<" \n"[i==n];
	return 0;
}

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