제출 #568148

#제출 시각아이디문제언어결과실행 시간메모리
568148valerikk자리 배치 (IOI18_seats)C++17
31 / 100
4100 ms227800 KiB
#include "seats.h" #include <set> #include <algorithm> using namespace std; const int M = 1005; const int N = 1e6 + 10; int h, w; int r[N], c[N]; set<int> sr[N], sc[N]; void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) { h = H, w = W; for (int i = 0; i < h * w; ++i) { r[i] = R[i], c[i] = C[i]; } for (int i = 0; i < h * w; ++i) { sr[r[i]].insert(i); sc[c[i]].insert(i); } } int swap_seats(int a, int b) { sr[r[a]].erase(a); sc[c[a]].erase(a); sr[r[b]].erase(b); sc[c[b]].erase(b); swap(r[a], r[b]); swap(c[a], c[b]); sr[r[a]].insert(a); sc[c[a]].insert(a); sr[r[b]].insert(b); sc[c[b]].insert(b); vector<pair<int, int>> v; for (int i = 0; i < h; ++i) { v.emplace_back(*sr[i].begin(), i + 1); } for (int i = 0; i < w; ++i) { v.emplace_back(*sc[i].begin(), -i - 1); } sort(v.begin(), v.end()); int res = 0; int minr = h - 1, maxr = 0, minc = w - 1, maxc = 0; for (int i = 0; i < h + w; ++i) { if (v[i].second > 0) { minr = min(minr, v[i].second - 1); maxr = max(maxr, v[i].second - 1); } else { minc = min(minc, -v[i].second - 1); maxc = max(maxc, -v[i].second - 1); } if (i == h + w - 1 || v[i].first < v[i + 1].first) { int s = (maxr - minr + 1) * (maxc - minc + 1); if (s >= v[i].first + 1 && (i == h + w - 1 || s <= v[i + 1].first)) { ++res; } } } 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...