Submission #375339

#	Time	Username	Problem	Language	Result	Execution time	Memory
375339		Kevin_Zhang_TW	Naan (JOI19_naan)	C++17	29 / 100	299 ms	95724 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 ( (num + v[ind][pos]) * n >= sum * i ) break;
			up = pos + 1, dn = 1;
			num += v[ind][pos];
		}
		ll pos = up / dn, val = v[ind][pos];

		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);
		}

		DE(mn.first, mn.second, ind);
		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 = 1;i+1 < n;++i) {
		DE(i);
		auto [ui, di] = res[i];
		auto [uj, dj] = res[i-1];
		DE(ui,di, uj,dj);
	}

	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];

}

Compilation message (stderr)

naan.cpp: In function 'int32_t main()':
naan.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
naan.cpp:90:3: note: in expansion of macro 'DE'
   90 |   DE(mn.first, mn.second, ind);
      |   ^~
naan.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
naan.cpp:100:3: note: in expansion of macro 'DE'
  100 |   DE(i);
      |   ^~
naan.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
naan.cpp:103:3: note: in expansion of macro 'DE'
  103 |   DE(ui,di, uj,dj);
      |   ^~
naan.cpp:101:8: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  101 |   auto [ui, di] = res[i];
      |        ^~~~~~~~
naan.cpp:102:8: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  102 |   auto [uj, dj] = res[i-1];
      |        ^~~~~~~~

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