Submission #1073804

#TimeUsernameProblemLanguageResultExecution timeMemory
1073804HorizonWestSeats (IOI18_seats)C++17
11 / 100
4059 ms47840 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[5001][5001]; 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); } } int tmp(int A, int B) { A++; B++; swap(v[A], v[B]); int a = Inf, b = 0, c = Inf, d = 0, ans = 0; for(int i = 1; i < v.size(); 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); ///if(B == 7) cerr << a << " " << b << " " << c << " " << d << endl; ans += (fx == i); } //swap(v[A], v[B]); return ans; } int swap_seats(int A, int B) { return tmp(A, 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; }

Compilation message (stderr)

seats.cpp: In function 'int tmp(int, int)':
seats.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i = 1; i < v.size(); i++)
      |                    ~~^~~~~~~~~~
#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...