Submission #1140031

#TimeUsernameProblemLanguageResultExecution timeMemory
1140031AbdullahIshfaqTiles (BOI24_tiles)C++20
15 / 100
23 ms5704 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define MOD 998244353 const int N = 1e6 + 5; int n, m; int a[N]; int b[N]; int c[1010][1010]; void solve(){ cin >> n >> m; int mx = 0; for(int i = 1; i <= n; i++){ cin >> a[i] >> b[i]; mx = max(mx, b[i]); } if(n <= 5){ int w = 0, h = 0; vector<int> xs, ys; for (int i = 1; i <= n; ++i) { xs.push_back(a[i]); ys.push_back(b[i]); } 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 << '\n'; } else { cout << (h % 2 ? xs.back() - 1 : xs.back()) << '\n'; } exit(0); } if(n == 6){ set<int> xs; map<int, vector<int>> mx; for (int i = 1; i <= n; ++i) { xs.insert(a[i]); mx[a[i]].push_back(b[i]); sort(mx[a[i]].begin(), mx[a[i]].end()); } int w1 = 0, w2 = 0, h1 = 0, h2 = 0, wmid = 0; int x1 = *xs.begin(); xs.extract(x1); int x2 = *xs.begin(); xs.extract(x2); 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 > w2) { // case 1 if (w1 % 2) { cout << 0; } else if (h1 % 2) { cout << x2 - 1; } else if (w2 % 2 == 1 || (w1 - w2) % 2 == 1) { cout << x2; } else if (h2 % 2) { cout << x3 - 1; } else { cout << x3; } } else { if (w1 % 2) { cout << 0; } else if (h1 % 2) { cout << x2 - 1; } else if (w2 % 2 == 1 || (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(a[k] == a[j] and a[j] == a[i]){ v.pop_back(); } else if(b[k] == b[j] and b[j] == b[i]){ v.pop_back(); } else{ break; } } v.push_back(i); } int ans = 0; for(int i: v){ if(b[i] % 2 or b[i] == 0){ break; } ans = a[i] - (a[i] % 2); if(a[i] % 2){ break; } } cout << ans << '\n'; } else{ for(int i = 1; i <= n; i++){ int j = i - 1; if(j == 0){ j = n; } if(a[i] == a[j]){ for(int y = min(b[i], b[j]); y + min(b[i], b[j]) < b[i] + b[j]; y++){ c[a[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...