Submission #375329

#TimeUsernameProblemLanguageResultExecution timeMemory
375329Kevin_Zhang_TWNaan (JOI19_naan)C++17
29 / 100
34 ms8044 KiB
#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; using opl = long long; int n, L; 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 (stderr)

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);
      |   ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...