Submission #720730

#	Time	Username	Problem	Language	Result	Execution time	Memory
720730		qwerasdfzxcl	Naan (JOI19_naan)	C++17	100 / 100	409 ms	86808 KiB

naan

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;

struct Frac{
	ll a, b;
	Frac(){}
	Frac(ll _a, ll _b): a(_a), b(_b) {}

	bool operator < (const Frac &F) const{
		return (__int128)a*F.b < (__int128)b*F.a;
	}
};

int n, m, used[2020];
ll a[2020];
vector<Frac> V[2020];

void input(int i){
	ll S = 0;
	for (int j=1;j<=m;j++){
		cin >> a[j];
		S += a[j];
	} 

	ll cur = S, c = 1, pt = 1;
	while(c<n){
		if (a[pt]*n < cur) {cur -= a[pt++]*n; continue;}
		V[c].emplace_back(cur + a[pt]*n*(pt-1), a[pt]*n);
		cur += S;
		c++;
	}

}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for (int i=1;i<=n;i++) input(i);

	vector<int> ans;
	for (int i=1;i<=n-1;i++){
		Frac mn(INF, 1);
		int idx = -1;

		for (int j=1;j<=n;j++) if (!used[j] && V[i][j-1] < mn){
			mn = V[i][j-1];
			idx = j;
		}

		ans.push_back(idx);
		used[idx] = 1;
		cout << mn.a << ' ' << mn.b << '\n';
	}

	for (int j=1;j<=n;j++) if (!used[j]) ans.push_back(j);
	for (auto &x:ans) cout << x << ' ';
}

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