| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 375346 |
2021-03-09T09:38:58 Z |
Kevin_Zhang_TW |
Naan (JOI19_naan) |
C++17 |
|
527 ms |
116888 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;
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];
}
| # |
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 |
1 ms |
384 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 |
2 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
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 |
1 ms |
492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 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 |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
492 KB |
Output is correct |
| 15 |
Correct |
1 ms |
492 KB |
Output is correct |
| 16 |
Correct |
1 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 |
29 ms |
492 KB |
Output is correct |
| 20 |
Correct |
1 ms |
492 KB |
Output is correct |
| 21 |
Correct |
46 ms |
512 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 |
| # |
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 |
1 ms |
384 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 |
2 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| 16 |
Correct |
1 ms |
364 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 |
512 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 |
384 KB |
Output is correct |
| 29 |
Correct |
1 ms |
492 KB |
Output is correct |
| 30 |
Correct |
1 ms |
492 KB |
Output is correct |
| 31 |
Correct |
1 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 |
29 ms |
492 KB |
Output is correct |
| 35 |
Correct |
1 ms |
492 KB |
Output is correct |
| 36 |
Correct |
46 ms |
512 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 |
37 ms |
12012 KB |
Output is correct |
| 44 |
Correct |
223 ms |
53996 KB |
Output is correct |
| 45 |
Correct |
145 ms |
21484 KB |
Output is correct |
| 46 |
Correct |
21 ms |
2924 KB |
Output is correct |
| 47 |
Correct |
163 ms |
34412 KB |
Output is correct |
| 48 |
Correct |
155 ms |
73708 KB |
Output is correct |
| 49 |
Correct |
57 ms |
23020 KB |
Output is correct |
| 50 |
Correct |
303 ms |
90220 KB |
Output is correct |
| 51 |
Correct |
174 ms |
37996 KB |
Output is correct |
| 52 |
Correct |
316 ms |
80108 KB |
Output is correct |
| 53 |
Correct |
259 ms |
76160 KB |
Output is correct |
| 54 |
Correct |
1 ms |
364 KB |
Output is correct |
| 55 |
Correct |
64 ms |
43756 KB |
Output is correct |
| 56 |
Correct |
215 ms |
52204 KB |
Output is correct |
| 57 |
Correct |
160 ms |
46060 KB |
Output is correct |
| 58 |
Correct |
221 ms |
74840 KB |
Output is correct |
| 59 |
Correct |
185 ms |
42076 KB |
Output is correct |
| 60 |
Correct |
522 ms |
116716 KB |
Output is correct |
| 61 |
Correct |
523 ms |
116588 KB |
Output is correct |
| 62 |
Correct |
503 ms |
116332 KB |
Output is correct |
| 63 |
Correct |
527 ms |
116888 KB |
Output is correct |
| 64 |
Correct |
511 ms |
116704 KB |
Output is correct |
| 65 |
Correct |
405 ms |
103404 KB |
Output is correct |
| 66 |
Correct |
393 ms |
103324 KB |
Output is correct |
| 67 |
Correct |
406 ms |
103532 KB |
Output is correct |
| 68 |
Correct |
198 ms |
60396 KB |
Output is correct |
| 69 |
Correct |
222 ms |
56684 KB |
Output is correct |
| 70 |
Correct |
226 ms |
72300 KB |
Output is correct |
| 71 |
Correct |
328 ms |
82284 KB |
Output is correct |
