Submission #1140047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140047		AbdullahIshfaq	Tiles (BOI24_tiles)	C++20	15 / 100	24 ms	5700 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 998244353
const int N = 2e5 + 5;
int n, m;
int a[N];
int b[N];
int c[1010][1010];
pair<int,int> tmp[N];
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){
		pair<pair<int,int>, int> mn = {{1e9, 0}, 0};
		for (int i = 1; i <= n; ++i) {
			mn = min(mn, {{a[i], b[i]}, i });
		}
		int cur_ind = 1;
		for (int j = mn.second; j <= n; ++j) {
			tmp[cur_ind] = {a[j], b[j]};
			++cur_ind;
		}
		for (int j = 1; j < mn.second; ++j) {
			tmp[cur_ind] = {a[j], b[j]};
			++cur_ind;
		}
		int cc = 0;
		++cc;
		a[cc] = tmp[1].first;
		b[cc] = tmp[1].second;
		pair<int,int> last = tmp[1];
		for (int i = 2; i < n; ++i) {
			if (((last.first == tmp[i].first && tmp[i].first == tmp[i + 1].first) || (last.second == tmp[i].second && tmp[i].second == tmp[i + 1].second))) continue;
			last = tmp[i];
			++cc;
			a[cc] = last.first;
			b[cc] = last.second;
		}
		++cc;
		a[cc] = tmp[n].first;
		b[cc] = tmp[n].second;
		n = cc;
		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.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 > w2) {
			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();
	}
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 9
• Subtask 3: 11 / 11
• Subtask 4: 0 / 19
• Subtask 5: 0 / 22
• Subtask 6: 0 / 25
• Subtask 7: 0 / 10