제출 #375346

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
375346		Kevin_Zhang_TW	Naan (JOI19_naan)	C++17	100 / 100	527 ms	116888 KiB

naan

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif 
const int MAX_N = 2005, inf = 1e9;

int n, L;

using lll = __int128;

#define int ll

pair<int,int> loc[MAX_N][MAX_N];

bool cmp(pair<int,int> a, pair<int,int> b) {
	return (lll)a.first * b.second < (lll)b.first * a.second;
}

int v[MAX_N][MAX_N];

void init(int ind) {
	int sum = 0;
	for (int i = 0;i < L;++i)
		sum += v[ind][i];

	int up = 0, dn = 1;
	int num = 0;

	for (int i = 1;i < n;++i) {
		while (true) {
			int pos = up / dn;
			// (v[ind][pos] + num) * n >= sum * i
			if (pos == L-1) {
				assert((num + v[ind][pos]) * n == sum * n);
			}
			if ( (num + v[ind][pos]) * n > sum * i ) break;
			up = pos + 1, dn = 1;
			num += v[ind][pos];
			assert(pos < L);

			//DE(i, pos, num);
		}
		ll pos = up / dn, val = v[ind][pos];
		assert(pos < L);

		up = sum * i - num * n, dn = val * n;
		up += pos * dn;

		loc[ind][i] = {up, dn};

		if (i>1) assert(cmp(loc[ind][i-1], loc[ind][i]));

	}
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> L;
	for (int i = 0;i < n;++i)
		for (int j = 0;j < L;++j)
			cin >> v[i][j];

	for (int i = 0;i < n;++i) {
		init(i);
	}

	vector<pair<int,int>> res;
	vector<int> od, vis(n);

	for (int i = 0;i+1 < n;++i) {

		pair<int,int> mn {inf, 1};
		int ind = -1;

		auto update = [&](int id) {
			if (cmp(loc[id][i+1], mn)) 
				ind = id, mn = loc[id][i+1];
		};

		for (int j = 0;j < n;++j) {
			if (!vis[j]) 
				update(j);
		}

		od.pb(ind);
		vis[ind] = true;
		res.pb(mn);

	}
	for (int i = 0;i < n;++i) if (!vis[i])
		od.pb(i);

	for (int i = 0;i+1 < n;++i) 
		cout << res[i].first << ' ' << res[i].second << '\n';
	for (int i = 0;i < n;++i)
		cout << od[i]+1 << " \n"[i+1==n];
}

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