Submission #1211768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211768		catch_me_if_you_can	Chessboard (IZhO18_chessboard)	C++20	100 / 100	495 ms	4832 KiB

chessboard

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 2e5+5;
const int INF = 1e17;

int m_ceil(int a, int b)
{
	if(a%b)
		return ((a/b)+1);
	else
		return a/b;
}

int m_floor(int a, int b)
{
	return a/b;
}

int intersect(int a, int b, int c, int d)
{
	int L = max(a, c);
	int R = min(b, d);
	if(L > R)
		return 0;
	return R-L+1; 
}

in solve1(int a, int b, int n)//{even, odd}
{
	//compute even - odd difference for reference.
	int L = b-a+1;
	int G = (b-a)/(2*n); G*=(2*n);
	b-=G;
	if(b >= (a+2*n))
		b-=(2*n);
	//[a, b]
	a%=(2*n);
	b%=(2*n);
	if(b < a)
		b+=(2*n);
	int g = intersect(a, b, 0, n-1) - intersect(a, b, n, 2*n-1) + intersect(a, b, 2*n, 3*n-1) - intersect(a, b, 3*n, 4*n-1);
	return {(g+L)/2, (L-g)/2};
}

in solve3(int ax, int bx, int ay, int by, int n)
{
	in a = {0,0};
	for(int i = ax; i <= bx; i++)
	{
		for(int j = ay; j <= by; j++)
		{
			int G = (i/n);
			int H = (j/n);
			G+=H;
			if(G%2 == 0)
				a[0]++;
			else
				a[1]++;
		}
	}
	return a;
}

in solve2(int ax, int bx, int ay, int by, int n)//see coloring as floor(i/k) + floor(j/k) mod 2. 
{
	auto x = solve1(ax, bx, n);
	auto y = solve1(ay, by, n);
	in z = {x[0]*y[0]+x[1]*y[1], x[0]*y[1]+x[1]*y[0]};
	return z;
}

int comp(const vector<array<int, 4>> &rect, int N)
{
	int ok = 0;
	for(auto [ax, bx, ay, by]: rect)
	{
		auto [X, Y] = solve2(ax, bx, ay, by, N);
		ok+=(X-Y);
	}
	return ok;
}

int win(const vector<array<int, 4>> &rect, int N, int n)
{
	int diff = comp(rect, N);
	//odd stuff is black. how many black?
	int g = n/N; g*=g; g/=2; g*=N; g*=N;
	return min(g + diff, n*n - g - diff);
}

signed main()
{
	fast();
	int n, k; cin >> n >> k;
	vector<array<int, 4>> rect;
	while(k--)
	{
		int ax, bx, ay, by; cin >> ax >> ay >> bx >> by;
		ax--; bx--; ay--; by--;
		rect.pb({ax, bx, ay, by});
	}
	int ans = INF;
	for(int i = 1; i*i <= n; i++)
	{
		if(n%i)
			continue;
		if(i == n)
			continue;
		ans = min(ans, win(rect, i, n));
		if(i != 1)
			ans = min(ans, win(rect, n/i, n));
	}
	cout << ans << "\n";
	return 0;
}	

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 23 / 23
• Subtask 6: 30 / 30