제출 #770507

#제출 시각아이디문제언어결과실행 시간메모리
770507cadmiumsky카니발 티켓 (IOI20_tickets)C++17
39 / 100
3077 ms133924 KiB
#include <bits/stdc++.h> #include "tickets.h" #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; using ld = long double; #define int ll #define sz(x) ((int)(x).size()) using pii = pair<int,int>; using tii = tuple<int,int,int>; const int nmax = 1500 + 5; void partition(int k, vector<vector<int>> wsign) { int n = sz(wsign), m = sz(wsign[0]); vector<pii> freq(n, pii{0, 0}); vector<deque<int>> sorted(n); vector<vector<signed>> rez(n, vector<signed>(m, -1)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) if(wsign[i][j] == -1) sorted[i].emplace_back(j), freq[i].first++; for(int j = 0; j < m; j++) if(wsign[i][j] == 1) sorted[i].emplace_back(j), freq[i].second++; } for(int Q = 0; Q < k; Q++) { vector<int> checked(n); vector<int> atr(n); iota(all(atr), 0); sort(all(atr), [&](auto a, auto b) { return freq[a].first > freq[b].first; }); for(int T = 0, cnt = 0; cnt < n / 2 && T < n; T++) { int i = atr[T]; if(checked[i]) continue; if(freq[i].first > 0) { rez[i][sorted[i].front()] = Q; sorted[i].pop_front(); cnt++; checked[i] = 1; freq[i].first--; } } sort(all(atr), [&](auto a, auto b) { return freq[a].second > freq[b].second; }); for(int T = 0, cnt = 0; cnt < n / 2 && T < n; T++) { int i = atr[T]; if(checked[i]) continue; if(freq[i].second > 0) { rez[i][sorted[i].back()] = Q; sorted[i].pop_back(); cnt++; checked[i] = 1; freq[i].second--; } } } allocate_tickets(rez); return; } const int inf = 1e9 + 5; const ll infll = 1e18 + 5; struct Flux { struct Edg { int other; ll cost; int flux, cap; }; vector<Edg> edg; vector<vector<int>> g; vector<int> p; vector<ll> pot; vector<ll> dist; vector<int> inque; vector<int> f; //vector<int> int S, T; void init(int s, int t, int n) { g.resize(n); pot.resize(n); dist.resize(n); inque.resize(n); f.resize(n); p.resize(n); S = s; T = t; } int addedg(int u, int v, int c, ll w) { g[u].emplace_back(sz(edg)); edg.emplace_back(Edg{v, w, 0, c}); g[v].emplace_back(sz(edg)); edg.emplace_back(Edg{u, -w, 0, 0}); return sz(edg) - 2; } void SPFA() { fill(all(dist), infll); fill(all(inque), 0); fill(all(f), -1); queue<int> que; inque[S] = 1; dist[S] = 0; p[S] = -1; f[S] = inf; que.emplace(S); while(!que.empty()) { auto node = que.front(); que.pop(); inque[node] = 0; for(auto e : g[node]) { if(edg[e].flux < edg[e].cap && dist[edg[e].other] > dist[node] + edg[e].cost) { dist[edg[e].other] = dist[node] + edg[e].cost; f[edg[e].other] = min(f[node], edg[e].cap - edg[e].flux); p[edg[e].other] = e; if(!inque[edg[e].other]) inque[edg[e].other] = 1, que.emplace(edg[e].other); } } } return; } void dijkstra() { fill(all(dist), infll); fill(all(f), -1); priority_queue<pii, vector<pii>, greater<pii>> heap; dist[S] = 0; p[S] = -1; f[S] = inf; heap.emplace(0, S); while(!heap.empty()) { auto [d, node] = heap.top(); heap.pop(); if(d != dist[node]) continue; for(auto e : g[node]) { int d2 = d + edg[e].cost + pot[node] - pot[edg[e].other]; if(edg[e].flux < edg[e].cap && dist[edg[e].other] > d2) { dist[edg[e].other] = d2; f[edg[e].other] = min(edg[e].cap - edg[e].flux, f[node]); p[edg[e].other] = e; heap.emplace(d2, edg[e].other); } } } for(int i = 0; i < sz(dist); i++) dist[i] += pot[i]; return; } bool dijk = 0; void SP() { if(!dijk) SPFA(); else dijkstra(); dijk = 1; } pair<ll,int> flux() { ll cost = 0; int flow = 0; while(true) { SP(); if(f[T] == -1) break; flow += f[T]; cost += (ll)f[T] * dist[T]; int current_edg = p[T]; while(current_edg != -1) { edg[current_edg].flux += f[T]; edg[current_edg ^ 1].flux -= f[T]; current_edg = p[edg[current_edg ^ 1].other]; } swap(pot, dist); } return pii{cost, flow}; } }; int N, M; int S() { return 0; } int T() { return 1; } int row(int k) { return 2 + k; } int cellp(int x, int y) { return 2 + N + x * M + y; } int cellm(int x, int y) { return 2 + N + N * M + x * M + y; } int Tp() { return 2 + N + N * M + N * M; } int Tm() { return 2 + N + N * M + N * M + 1; } ll S2(signed k, vector<vector<signed>> d) { vector<pii> values; int n = sz(d), m = sz(d[0]); N = n; M = m; vector<vector<int>> atrp(n, vector<int>(m, 0)); vector<vector<int>> atrm(n, vector<int>(m, 0)); Flux flux; flux.init(S(), T(), Tm() + 5); for(int i = 0; i < n; i++) { flux.addedg(S(), row(i), k, 0); for(int j = 0; j < m; j++) { atrp[i][j] = flux.addedg(row(i), cellp(i, j), 1, -d[i][j]); flux.addedg(cellp(i, j), Tp(), 1, 0); atrm[i][j] = flux.addedg(row(i), cellm(i, j), 1, d[i][j]); flux.addedg(cellm(i, j), Tm(), 1, 0); } } flux.addedg(Tm(), T(), n / 2 * k, 0); flux.addedg(Tp(), T(), n / 2 * k, 0); auto [sum, f] = flux.flux(); sum *= -1; vector<int> freq(n); vector<vector<int>> signs(n, vector<int>(m, 0)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(flux.edg[atrp[i][j]].flux == 1) signs[i][j] = 1; if(flux.edg[atrm[i][j]].flux == 1) signs[i][j] = -1; } } partition(k, signs); return sum; } ll S3(signed k, vector<vector<signed>> d) { int n = sz(d), m = sz(d[0]); vector<pii> freq(n, pii{0, 0}); vector<deque<int>> sorted(n); vector<vector<signed>> rez(n, vector<signed>(m, -1)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) if(d[i][j] == 0) sorted[i].emplace_back(j), freq[i].first++; for(int j = 0; j < m; j++) if(d[i][j] == 1) sorted[i].emplace_back(j), freq[i].second++; } ll sum = 0; for(int Q = 0; Q < k; Q++) { vector<int> checked(n); vector<int> atr(n); iota(all(atr), 0); sort(all(atr), [&](auto a, auto b) { return freq[a].first > freq[b].first; }); int total = 0; for(int T = 0, cnt = 0; cnt < n / 2 && T < n; T++) { int i = atr[T]; if(checked[i]) continue; if(freq[i].first > 0) { rez[i][sorted[i].front()] = Q; sorted[i].pop_front(); cnt++; checked[i] = 1; freq[i].first--; } } sort(all(atr), [&](auto a, auto b) { return freq[a].second > freq[b].second; }); for(int T = 0, cnt = 0; cnt < n / 2 && T < n; T++) { int i = atr[T]; if(checked[i]) continue; if(freq[i].second > 0) { total++; rez[i][sorted[i].back()] = Q; sorted[i].pop_back(); cnt++; checked[i] = 1; freq[i].second--; } } for(int T = 0; T < n; T++) { int i = atr[T]; if(checked[i]) continue; if(freq[i].second > 0) total++, freq[i].second--; else freq[i].first--; rez[i][sorted[i].back()] = Q; sorted[i].pop_back(); checked[i] = 1; } sum += min(total, n - total); } allocate_tickets(rez); return sum; } ll S4(signed k, vector<vector<signed>> d) { vector<pii> values; int n = sz(d), m = sz(d[0]); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) values.emplace_back(i, j); sort(all(values), [&](auto a, auto b) { return d[a.first][a.second] < d[b.first][b.second]; }); vector<vector<int>> signs(n, vector<int>(m, 1)); for(int i = 0; i < n / 2 * k; i++) signs[values[i].first][values[i].second] = -1; partition(k, signs); ll sum = 0; for(auto [a, b] : values) { sum += d[a][b] * signs[a][b]; } return sum; } ll S1(signed k, vector<vector<signed>> d) { int n = sz(d), m = 1; vector<vector<signed>> rez(n, vector<signed>(m, 0)); allocate_tickets(rez); vector<int> v; for(auto a : d) for(auto x : a) v.emplace_back(x); sort(all(v)); ll sum = 0; for(int i = 0; i < n; i++) sum += v[i]; for(int i = 0; i < n / 2; i++) sum -= 2 * v[i]; return sum; } long long find_maximum(signed k, std::vector<std::vector<signed>> d) { bool ok = 1; for(auto a : d) for(auto x : a) ok &= (x == 0 || x == 1); if(sz(d[0]) == 1) return S1(k, d); if(k == sz(d[0])) return S4(k, d); if(ok) return S3(k, d); else return S2(k, d); } #undef int /** Anul asta se da centroid. -- Surse oficiale */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...