제출 #1170440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170440		jakubmz2	Naan (JOI19_naan)	C++20	0 / 100	0 ms	324 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<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];
		}
		//cout << s << " s\n";
		ll curr = 0;
		ll j = 1;
		for(ll w = 1; w <= k; ++w){
			if(j >= n) break;
			if((curr + tab[w]) * n < j * s){
				cout << "#\n";
				curr += tab[w];
				continue;
			}
			koniec[i][j] = {j * s - curr * n, tab[w] * n};
			if(koniec[i][j].first < 0){
				koniec[i][j] = {1,2};
			}
			//cout << koniec[i][j].first << " " << koniec[i][j].second << " k1\n";
			ll g = __gcd(koniec[i][j].first, koniec[i][j].second);
			koniec[i][j].first /= g;
			koniec[i][j].second /= g;
			koniec[i][j].first += (w-1) * koniec[i][j].second;
			
			g = __gcd(koniec[i][j].first, koniec[i][j].second);
			koniec[i][j].first /= g;
			koniec[i][j].second /= g;			
			//cout << "i " << i << " j " << j << " " << koniec[i][j].first << " " << koniec[i][j].second << " k2\n";
			curr += tab[w];
			j++;
		}
	}
	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: 0 / 5
• Subtask 2: 0 / 24
• Subtask 3: 0 / 71