Submission #1170457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170457		jakubmz2	Naan (JOI19_naan)	C++20	100 / 100	504 ms	63296 KiB

naan

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

const ll MAXN = 2e3 + 5;

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

pair<ll,ll> 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){
		ll s = 0;
		for(ll j = 1; j <= k; ++j){
			cin >> tab[j];
			//cout << j << " " << tab[j] << "tab\n";
			s += tab[j];
			tab[j] *= n;
		}
		//cout << s << " s\n";
		ll curr = 0;
		ll j = 1;
		for(ll w = 1; w < n; ++w){
			curr += s;
			while(tab[j] <= curr){
				curr -= tab[j];
				j++;
			}
			koniec[i][w] = {curr, tab[j]};
			ll g = __gcd(koniec[i][w].first, koniec[i][w].second);
			koniec[i][w].first /= g;
			koniec[i][w].second /= g;
			koniec[i][w].first += (j-1) * koniec[i][w].second;
		}
	}
	for(ll i = 1; i < n; ++i){
		pair<ll,ll> curr = {k + 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: 71 / 71