Submission #375280

#	Time	Username	Problem	Language	Result	Execution time	Memory
375280		Kevin_Zhang_TW	Naan (JOI19_naan)	C++17	0 / 100	1 ms	364 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;

const ll sc = 1e5;

#define ptr asidjfpoasijf
#define go sdf89jc

ll a[MAX_N][MAX_N];

ll sum[MAX_N], ptr[MAX_N], cursum[MAX_N];

int n, L;

void go(int id) {
	ll &j = ptr[id];
	ll need = (sum[id] + n-1) / n;
	while (cursum[id] < need && j < (L * sc)) {
		int atid = j / sc;
		ll lft = sc - (j % sc);
		if ((a[id][atid] * lft + cursum[id]) >= need)
			break;
		cursum[id] += a[id][atid] * lft;
		j += lft;
	}
	int atid = j / sc;
	if (atid != L) {
		ll ext = (need - cursum[id] + a[id][atid]-1) / a[id][atid];
		j += ext;
	}
}

void cut(ll pos) {
	static ll lst;
	int ind = lst / sc, r = pos / sc;
	ll len = min(sc - lst % sc, pos - lst);
	DE(lst, pos);
	for (int i = 0;i < n;++i) {
		cursum[i] -= len * a[i][ind];
	}
	for (int i = ind + 1;i < r;++i) {
		cursum[i] -= sc * a[i][ind];
	}
	if (ind != r) {
		len = pos % sc;
		ind = r;
		for (int i = 0;i < n;++i) {
			cursum[i] -= len * a[i][ind];
		}
	}
	lst = pos;
	for (int i = 0;i < n;++i) go(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 >> a[i][j];
			sum[i] += a[i][j] * sc;
		}
		a[i][L] = sc * 100000ll;
	}

	vector<int> od;
	vector<ll> sep{0};
	vector<int> vis(n);
	
	for (int i = 0;i < n;++i) {
		cut(sep.back());
		ll pos = LLONG_MAX;
		int id = -1;
		for (int j = 0;j < n;++j) if (!vis[j])
			if (chmin(pos, ptr[j]))
				id = j;
		sep.pb(pos);
		od.pb(id);
		vis[id] = true;
	}


	for (int i = 1;i < n;++i) {
		ll a = sep[i], b = sc;
		cout << a << ' ' << b << '\n';
	}
	for (int i = 0;i < n;++i)
		cout << od[i] << " \n"[i+1==n];
}

Compilation message (stderr)

naan.cpp: In function 'void cut(ll)':
naan.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
naan.cpp:52:2: note: in expansion of macro 'DE'
   52 |  DE(lst, pos);
      |  ^~

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