Submission #112233

#	Time	Username	Problem	Language	Result	Execution time	Memory
112233		zscoder	Naan (JOI19_naan)	C++17	100 / 100	620 ms	108280 KiB

naan

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

ii reduce(ii a)
{
	ll g=__gcd(a.fi,a.se);
	a.fi/=g; a.se/=g;
	return a;
}

bool cmp(ii a, ii b)
{
	ll s1 = a.fi/a.se; ll s2 = b.fi/b.se;
	if(s1!=s2) return s1<s2;
	a.fi%=a.se; b.fi%=b.se;
	return (a.fi*b.se<=a.se*b.fi);
}

ii add(ii a, ii b)
{
	ll s1 = a.fi/a.se; ll s2 = b.fi/b.se;
	s1+=s2;
	a.fi%=a.se; b.fi%=b.se;
	ii c;
	if(a.se==b.se) c=mp(a.fi+b.fi,a.se);
	else c = mp(a.fi*b.se+a.se*b.fi,a.se*b.se);
	c.fi+=s1*c.se;
	return c;
}

ll a[2222][2222];
ll S[2222];
ii cutpoint[2222][2222];
bool used[2222];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,m; cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>a[i][j];
			S[i]+=a[i][j];
		}
	}
	for(int i=0;i<n;i++)
	{
		int cur=0; ll cur_left =a[i][0]*n;
		ii len=mp(0,1);
		//search for the first place sum=j
		for(int j=0;j<n;j++)
		{
			ll required = S[i];
			while(required>0)
			{
				if(cur_left<=required)
				{
					required-=cur_left;
					cur_left=0;
					len=mp(cur+1,1);
					cur++; 
					if(cur<m) cur_left+=a[i][cur]*n;
				}
				else
				{
					cur_left-=required;
					len=add(len,mp(required,a[i][cur]*n));
					required=0;
				}
			}
			cutpoint[i][j]=len;
			assert(len.se<=ll(1e9));
			//cerr<<i<<' '<<j<<' '<<cutpoint[i][j].fi<<' '<<cutpoint[i][j].se<<'\n';
		}
	}
	vector<ii> ans;
	vi vec;
	for(int j=0;j<n;j++)
	{
		ii minpt = mp(-1,-1); int id=-1;
		for(int i=0;i<n;i++)
		{
			if(used[i]) continue;
			if(minpt.fi<0) 
			{
				minpt=cutpoint[i][j]; id=i;
			}
			else if(cmp(cutpoint[i][j],minpt)) 
			{
				minpt=cutpoint[i][j]; id=i;
			}
		}
		vec.pb(id);
		ans.pb(minpt);
		used[id]=1;
	}
	for(int i=0;i<n-1;i++)
	{
		cout<<ans[i].fi<<' '<<ans[i].se<<'\n';
	}
	for(int i=0;i<n;i++)
	{
		cout<<vec[i]+1;
		if(i+1<n) cout<<' ';
	}
	cout<<'\n';
}

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