Submission #492818

#	Time	Username	Problem	Language	Result	Execution time	Memory
492818		jiahng	Naan (JOI19_naan)	C++14	29 / 100	230 ms	15916 KiB

naan

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int __int128
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
#define f first
#define s second
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
//~ #define lbd(x, y) lower_bound(all(x), y)
//~ #define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef pair <pi,int> pii;
typedef long double ld;
#define maxn 2010
#define INF (ll)1e18
int MOD;
int32_t N, L, A[maxn][maxn];
bool done[maxn];
struct frac{
	int a, b;
	frac(int _a,int _b){
		assert(_b != 0);
		a = _a, b = _b;
		int x = __gcd(a,b); a /= x; b /= x;
	}
	frac operator+(frac y){
		return frac(y.a * b + y.b * a, y.b * b);
	}
	frac operator-(frac y){
		y.a *= -1;
		return *this + y;
	}
	frac operator/(int y){
		return frac(a, b * y);
	}
	frac operator*(int y){
		return frac(a*y,b);
	}
	frac operator*(frac y){
		return frac(a*y.a,b*y.b);
	}
	bool operator<(frac y){
		return (__int128) a * y.b < (__int128) b * y.a;
	}
	bool operator>=(frac y){
		return (__int128) a * y.b >= (__int128) b * y.a;
	}
};
vector <frac> B[maxn];

int32_t main(){
	fast;

	cin >> N >> L;
	FOR(i,1,N) FOR(j,1,L) cin >> A[i][j];
	
	FOR(i,1,N){
		int sm = accumulate(A[i]+1,A[i] + L + 1, 0LL);
		frac cur = frac(0, 1);
		int idx = 1;
		FOR(j,1,L){
			while (cur + frac(A[i][j],1) >= frac(idx*sm, N)){
				B[i].pb(frac(j-1, 1) + (frac(idx*sm,N) - cur) / A[i][j]);
				idx++;
			}
			cur = cur + frac(A[i][j], 1);
		}
	}
	//~ FOR(i,1,N){
		//~ cout << "Person " << i << '\n';
		//~ aFOR(j,B[i]){
			//~ cout << j.a << ' ' << j.b << '\n';
		//~ }
	//~ }
	//~ return 0;
	vector <frac> ans; vector <int32_t> P;
	FOR(i,0,N-2){
		int nxt = -1; 
		FOR(j,1,N) if (!done[j] && (nxt == -1 || B[j][i] < B[nxt][i])) nxt = j;
		done[nxt] = 1;
		//~ assert(nxt != -1 && i < B[nxt].size());
		ans.pb(B[nxt][i]);
		P.pb(nxt);
	}
	FOR(i,1,N) if (!done[i]) P.pb(i);
	aFOR(i,ans){
		cout << int32_t(i.a) << ' ' << int32_t(i.b) << '\n';
	}
	aFOR(i,P) cout << i << ' ';
	
}

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