Submission #200052

#TimeUsernameProblemLanguageResultExecution timeMemory
200052EntityITNaan (JOI19_naan)C++14
100 / 100
509 ms101020 KiB
#include<bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() #define sz(x) ( (int)(x).size() ) using LL = long long; mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() ); int main() { ios_base::sync_with_stdio(0); cin.tie(0); #ifdef FourLeafClover freopen("input", "r", stdin); #endif // FourLeafCLover int n, L; cin >> n >> L; vector<vector<int> > v(n, vector<int>(L) ); for (int i = 0; i < n; ++i) { for (int j = 0; j < L; ++j) cin >> v[i][j]; } vector<vector<pair<LL, int> > > cut(n, vector<pair<LL, int> >(n) ); for (int i = 0; i < n; ++i) { int sum = accumulate(all(v[i]), 0); int cur = 0, pter = 0; for (int j = 0; j < n; ++j) { while ( (LL)cur * n < (LL)sum * (j + 1)) cur += v[i][pter++]; cut[i][j] = { (LL)pter * n * v[i][pter - 1] - (LL)cur * n + (LL)sum * (j + 1), n * v[i][pter - 1] }; } } auto smaller = [&](const pair<LL, int> &a, const pair<LL, int> &b) { return (double)a.first / a.second < (double)b.first / b.second; }; vector<bool> inAns(n, false); vector<int> ans; for (int i = 0; i < n; ++i) { int choo = -1; for (int j = 0; j < n; ++j) if (!inAns[j]) { if (choo == -1 || smaller(cut[j][i], cut[choo][i]) ) choo = j; } ans.emplace_back(choo); inAns[ans.back()] = true; } for (int i = 0; i < n - 1; ++i) cout << cut[ ans[i] ][i].first << ' ' << cut[ ans[i] ][i].second << '\n'; for (int i : ans) cout << i + 1 << ' '; cout << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...