Submission #1140092

#TimeUsernameProblemLanguageResultExecution timeMemory
1140092AbdullahIshfaqTiles (BOI24_tiles)C++20
13 / 100
23 ms8776 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define MOD 998244353 const int N = 2e5 + 5; int n, m; int xx[N]; int yy[N]; int c[1010][1010]; pair<int,int> a[N], b[N]; void solve(){ cin >> n >> m; int mx = 0; for(int i = 1; i <= n; i++){ cin >> xx[i] >> yy[i]; mx = max(mx, yy[i]); a[i] = {xx[i], yy[i]}; } pair<pair<int,int>, int> mn = {{1e9,0},0 }; for (int i = 1; i <= n; i++) { mn = min(mn, {a[i], i}); } int cur_ind = 1; for (int j = mn.second; j <= n; j++) { b[cur_ind] = a[j]; cur_ind++; } for (int j = 1; j < mn.second; j++) { b[cur_ind] = a[j]; cur_ind++; } int cc = 0; cc++; a[cc] = b[1]; pair<int,int> last = b[1]; for (int i = 2; i < n; i++) { if (((last.first == b[i].first and b[i].first == b[i + 1].first) or (last.second == b[i].second and b[i].second == b[i + 1].second))) continue; last = b[i]; cc++; a[cc] = last; } cc++; a[cc] = b[n]; n = cc; if(n <= 5){ int w = 0, h = 0; vector<int> xs, ys; for (int i = 1; i <= n; ++i) { xs.push_back(a[i].first); ys.push_back(a[i].second); } sort(xs.begin(), xs.end()); sort(ys.begin(), ys.end()); w = ys.back() - ys[0]; h = xs.back() - xs[0]; if (w % 2) { cout << 0; } else { cout << (h % 2 ? xs.back() - 1 : xs.back()); } exit(0); } if(n == 6){ set<int> xs; map<int, vector<int>> mx; for (int i = 1; i <= n; i++) { xs.insert(a[i].first); mx[a[i].first].push_back(a[i].second); sort(mx[a[i].first].begin(), mx[a[i].first].end()); } int w1 = 0, w2 = 0, h1 = 0, h2 = 0, wmid = 0; int x1 = *xs.begin(); xs.erase(xs.begin()); int x2 = *xs.begin(); xs.erase(xs.begin()); int x3 = *xs.begin(); w1 = mx[x1][1] - mx[x1][0]; w2 = mx[x3][1] - mx[x3][0]; h1 = x2 - x1, h2 = x3 - x2; if (w1 % 2) { cout << 0; } else if (h1 % 2) { cout << x2 - 1; } else if (w2 % 2 == 1 or abs(w2 - w1) % 2 == 1) { cout << x2; } else if (h2 % 2) { cout << x3 - 1; } else { cout << x3; } exit(0); } if(m > 1000 or mx > 1000){ vector<int> v; for(int i = 2; i <= n; i++){ while(v.size() > 1){ int k = v[v.size() - 2], j = v.back(); if(xx[k] == xx[j] and xx[j] == xx[i]){ v.pop_back(); } else if(yy[k] == yy[j] and yy[j] == yy[i]){ v.pop_back(); } else{ break; } } v.push_back(i); } int ans = 0; for(int i: v){ if(yy[i] % 2 or yy[i] == 0){ break; } ans = xx[i] - (xx[i] % 2); if(xx[i] % 2){ break; } } cout << ans << '\n'; } else{ for(int i = 1; i <= n; i++){ int j = i - 1; if(j == 0){ j = n; } if(xx[i] == xx[j]){ for(int y = min(yy[i], yy[j]); y + min(yy[i], yy[j]) < yy[i] + yy[j]; y++){ c[xx[i]][y] ^= 1; } } } for(int i = 1; i < m; i++){ for(int j = 0; j <= 1000; j++){ c[i][j] ^= c[i-1][j]; } } int ans = 0; for(int i = 0; i < m; i++){ int ok = 0; for(int j = 0; j <= 1000; j++){ if(c[i][j]){ ok = 1; if(c[i+1][j] and c[i][j+1] and c[i+1][j+1]){ c[i][j] = 0; c[i+1][j] = 0; c[i][j+1] = 0; c[i+1][j+1] = 0; } else{ ok = 2; break; } } } if(ok == 2){ break; } if(ok == 1){ continue; } ans = i + 1; } cout << ans; } } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int tests = 1; // cin >> tests; for(int i = 1; i <= tests; i++){ solve(); } }
#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...