제출 #316163

#제출 시각아이디문제언어결과실행 시간메모리
316163srvlt카니발 티켓 (IOI20_tickets)C++14
11 / 100
2 ms768 KiB
#include "tickets.h" #include <bits/stdc++.h> #define ll long long #define pb push_back #define SZ(x) (int)(x).size() #define all(x) begin(x), end(x) using namespace std; int n, m; set <array <int, 3>> st; vector <vector <int>> a, ans; vector <int> l, r; ll res; void erase(int x, int y) { st.erase({a[x][y], x, y}); if (l[x] == y) st.erase({a[x][r[x]], x, r[x]}), l[x]++; else st.erase({a[x][l[x]], x, l[x]}), r[x]--; } void connect(int i, array <int, 3> & x, array <int, 3> & y) { //cerr << "res += |" << x[0] << " - " << y[0] << "|\n"; res += abs(x[0] - y[0]); int A = x[1], B = x[2]; int C = y[1], D = y[2]; ans[A][B] = ans[C][D] = i; erase(A, B), erase(C, D); } ll find_maximum(int k, vector<vector<int>> A) { st.clear(), ans.clear(); n = A.size(), m = A[0].size(), a = A; l = vector <int>(n, 0), r = vector <int>(n, m - 1); res = 0; for (int i = 0; i < n; i++) ans.push_back(vector <int>(m, -1)); for (int it = 0; it < k; it++) { st.clear(); for (int i = 0; i < n; i++) { int L = l[i], R = r[i]; if (L > R) continue; st.insert({a[i][L], i, L}); if (L != R) st.insert({a[i][R], i, R}); } while (SZ(st) > 1) { auto x = *begin(st), y = *(--end(st)); if (x[1] == y[1]) { assert(SZ(st) > 2); auto x2 = *(++begin(st)), y2 = *(prev(--end(st))); if (abs(x[0] - y2[0]) > abs(x2[0] - y[0])) connect(it, x, y2); else connect(it, x2, y); } else connect(it, x, y); } } allocate_tickets(ans); return res; }
#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...