oj.uz

Submission #375330

# Submission time Handle Problem Language Result Execution time Memory
375330 2021-03-09T09:20:57 Z Kevin_Zhang_TW Naan (JOI19_naan) C++17
29 / 100
 211 ms 63928 KB 
#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;

#define int ll

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

bool cmp(pair<int,int> a, pair<int,int> b) {
	return (ll)a.first * b.second < (ll)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];
		}
		int pos = up / dn, val = v[ind][pos];

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

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

	}
}

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) {
			DE(loc[id][i+1].first, loc[id][i+1].second);
			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 = 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

naan.cpp: In lambda function:
naan.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
naan.cpp:77:4: note: in expansion of macro 'DE'
   77 |    DE(loc[id][i+1].first, loc[id][i+1].second);
      |    ^~
naan.cpp: In function 'int32_t main()':
naan.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
naan.cpp:87:3: note: in expansion of macro 'DE'
   87 |   DE(mn.first, mn.second, ind);
      |   ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 492 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 500 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 2 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 492 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Correct 1 ms 492 KB Output is correct
22 Correct 1 ms 492 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 492 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 492 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 500 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 492 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 492 KB Output is correct
25 Correct 1 ms 492 KB Output is correct
26 Correct 1 ms 492 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 492 KB Output is correct
30 Correct 1 ms 492 KB Output is correct
31 Correct 2 ms 492 KB Output is correct
32 Correct 1 ms 492 KB Output is correct
33 Correct 1 ms 492 KB Output is correct
34 Correct 1 ms 492 KB Output is correct
35 Correct 1 ms 492 KB Output is correct
36 Correct 1 ms 492 KB Output is correct
37 Correct 1 ms 492 KB Output is correct
38 Correct 1 ms 364 KB Output is correct
39 Correct 1 ms 492 KB Output is correct
40 Correct 1 ms 364 KB Output is correct
41 Correct 1 ms 364 KB Output is correct
42 Correct 1 ms 492 KB Output is correct
43 Correct 34 ms 12012 KB Output is correct
44 Incorrect 211 ms 63928 KB X_i is not increasing
45 Halted 0 ms 0 KB -