Submission #524387

#	Time	Username	Problem	Language	Result	Execution time	Memory
524387		ymm	Naan (JOI19_naan)	C++17	29 / 100	38 ms	17988 KiB

naan

///
///   Oh? You're approaching me?
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

struct frac{
	ll a, b;
	frac(){a=0;b=1;}
	frac(ll x){a=x;b=1;}
	frac(ll x, ll y){a=x;b=y;}
};
void gd(frac f){assert(f.a >= 0 && f.b > 0);}
frac red(frac f){ll g = gcd(f.a, f.b); return {f.a/g, f.b/g};}
frac operator+(frac a, frac b){return red({a.a*b.b + b.a*a.b, a.b*b.b});}
frac operator-(frac a, frac b){return red({a.a*b.b - b.a*a.b, a.b*b.b});}
frac operator*(frac a, frac b){return red({a.a*b.a, a.b*b.b});}
frac operator/(frac a, frac b){return red({a.a*b.b, a.b*b.a});}
bool operator<(frac a, frac b){return a.a*b.b < b.a*a.b;}
bool operator<=(frac a, frac b){return a.a*b.b <= b.a*a.b;}
ll flr(frac a){return a.a/a.b;}
ll cil(frac a){return (a.a + a.b - 1)/a.b;}

const int N = 2022;
ll v[N][N]; ll ps[N][N];
bool done[N];
ll n, m;

frac nxt(frac f, int i){
	f = red(f);
	assert(f.b <= 1e9+10);
	//gd(cil(f)-f);
	frac sm = (cil(f)-f)*v[i][flr(f)];
	frac tsm = frac(ps[i][m])/n;
	//assert(flr(f)<m);
	if(tsm <= sm) return f + tsm/v[i][flr(f)];
	ll l = cil(f);
	//assert((tsm-sm).a > 0);
	ll r = lower_bound(ps[i], ps[i]+m+1, cil(tsm-sm+ps[i][l]))-ps[i];
	if(r==m+1) return m+1;
	--r;
	//assert(r>=0 && v[i][r]>0);
	sm = sm+ps[i][r]-ps[i][l];
	return r + (tsm - sm)/v[i][r];
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	long long tmp;
	cin >> tmp; n=tmp;
	cin >> tmp; m=tmp;
	Loop(i,0,n) Loop(j,0,m){
		cin >> tmp;
		v[i][j]=tmp;
		ps[i][j+1] = ps[i][j]+v[i][j];
	}
	frac cur = 0;
	vector<pair<frac,int>> vec;
	Loop(i,0,n) {
		frac mn = m+1;
		int mni = -1;
		Loop(j,0,n){
			if(done[j]) continue;
			frac f = red(nxt(cur, j));
			if(f < mn){
				mn = f;
				mni = j;
			}
		}
		if(mni==-1) Kill(-1);
		done[mni]=1;
		vec.push_back({mn,mni});
		cur=mn;
	}
	Loop(i,0,n-1){
		cout << (long long)vec[i].first.a << ' ' << (long long)vec[i].first.b << '\n';
	}
	Loop(i,0,n) cout << vec[i].second+1 << ' ';
	cout << '\n';
}

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