Submission #1170429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170429		jakubmz2	Naan (JOI19_naan)	C++20	29 / 100	44 ms	10824 KiB

naan

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll MAXN = 2e3 + 5;

ll off[MAXN];
ll P[MAXN];
pair<ll,ll> ans[MAXN];

pair<__int128,__int128> koniec[MAXN][MAXN];

ll tab[MAXN];

bool comp(pair<ll,ll> a, pair<ll,ll> b){
	__int128 k = a.first;
	__int128 l = a.second;
	__int128 m = b.first;
	__int128 n = b.second;
	return k * n < m * l;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n, k;
	cin >> n >> k;
	ll x;
	for(ll i = 1; i <= n; ++i){
		__int128 s = 0;
		for(ll j = 1; j <= k; ++j){
			cin >> tab[j];
			//cout << j << " " << tab[j] << "tab\n";
			s += tab[j];
		}
		//cout << s << " s\n";
		__int128 curr = 0;
		__int128 j = 1;
		for(__int128 w = 1; w < k; ++w){
			//cout << w << " w\n";
			//cout << curr << " " << tab[w] << " " << n << " " << j << " " << s << "\n";
			if((curr + tab[w]) * n < j * s){
				curr += tab[w];
				//cout << "#\n";
				continue;
			}
			//cout << w << " " << tab[w] << " " << n << " tab\n";
			//cout << j * s << " " << curr * n << " " << tab[w] * n << " wyn\n";
			koniec[i][j] = {j * s - curr * n, tab[w] * n};
			__int128 g = __gcd(koniec[i][j].first, koniec[i][j].second);
			//cout << koniec[i][j].first << " " << koniec[i][j].second << " k1\n";
			//cout << g << " g\n";
			koniec[i][j].first /= g;
			koniec[i][j].second /= g;
			//cout << koniec[i][j].first << " " << koniec[i][j].second << " k2\n";
			koniec[i][j].first += (w-1) * koniec[i][j].second;
			curr += tab[j];
			//cout << koniec[i][j].first << " " << koniec[i][j].second << " k3\n";
			j++;
		}
	}
	for(ll i = 1; i < n; ++i){
		pair<ll,ll> curr = {k*1ll + 2ll, 1ll};
		ll v = -1;
		for(ll kd = 1; kd <= n; ++kd){
			if(off[kd] == 1) continue;
			if(comp(koniec[kd][i], curr)){
				curr = koniec[kd][i];
				v = kd;
			}
		}
		P[i] = v;
		off[v] = 1;
		ans[i] = curr;
	}
	for(ll i = 1; i < n; ++i){
		cout << ans[i].first << " " << ans[i].second << "\n";
	}
	for(int i = 1; i <= n; ++i){
		if(off[i] == 0) P[n] = i;
	}
	for(int i = 1; i <= n; ++i){
		cout << P[i] << " ";
	}
	cout << "\n";
	return 0;
}

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