Submission #1073767

#TimeUsernameProblemLanguageResultExecution timeMemory
1073767HorizonWestSeats (IOI18_seats)C++17
0 / 100
156 ms48212 KiB
#include <iostream> #include <complex> #include <iomanip> #include <vector> #include <algorithm> #include <functional> #include <bitset> #include <queue> #include <map> #include <stack> #include <cmath> #include <cstdint> using namespace std; #define endl '\n' #define db double #define ll long long #define pb push_back #define fs first #define sd second #define Mod long(1e9 + 7) #define all(x) x.begin(), x.end() #define unvisited long(-1) #define Eps double(1e-9) #define _for(i, n) for(int i = 0; i < (n); i++) #define dbg(x) cout << #x ": " << x << endl; const int Max = 1e6 + 7, Inf = 1e9 + 7; struct rectangle{ int a, b, c, d; rectangle(int i, int j, int k, int l){ a = i; b =j; c = k; d = l; } }; vector <pair<int, int>> v; vector <rectangle> t; vector <int> s; int m[23][23]; void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) { int a = Inf, b = 0, c = Inf, d = 0; t.push_back({ a, b, c, d }); s.push_back(0); v.push_back({ 0, 0 }); for(int i = 0; i < H*W; i++){ v.push_back({ R[i], C[i] }); a = min(a, v[i+1].fs); b = max(b, v[i+1].fs); c = min(c, v[i+1].sd); d = max(d, v[i+1].sd); t.push_back({ a, b, c, d }); int fx = (b-a+1) * (d-c+1); s.push_back(0); s[i+1] += s[i] + (i+1 == fx); m[R[i]][C[i]] = i+1; } } int swap_seats(int A, int B) { A++; B++; if(A > B) swap(A, B); int ans = s[A-1] + s.back() - s[B]; int a = t[A-1].a, b = t[A-1].b, c = t[A-1].c, d = t[A-1].d; swap(v[A], v[B]); for(int i = A; i <= B; i++){ a = min(a, v[i].fs); b = max(b, v[i].fs); c = min(c, v[i].sd); d = max(d, v[i].sd); int fx = (b-a+1) * (d-c+1); ans += (i == fx); } swap(v[A], v[B]); return ans; }
#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...