Submission #174039

#	Time	Username	Problem	Language	Result	Execution time	Memory
174039		anakib1	Chessboard (IZhO18_chessboard)	C++17	70 / 100	2054 ms	3704 KiB

chessboard

/*

Sviatoslav Bidzilia 2019
CF: anakib1

*/

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <chrono>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <deque>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdarg.h>
#include <utility>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define ull unisgned long long
#define ld long double
#define all(a) a.begin(), a.end()
#define SORT(a) sort(all(a))
#define pii pair<int, int>
#define tii triple<int, int, int>
#define e 1e-7
#define PI acos(-1)
#define inf 1e17
#define vi vector<int>
#define F first
#define S second
#define rng(x) for(int _ = 0; _ < (x); _++)
#define rngi(i, x) for(int i = 0; i < (x); i++)
#define rngsi(s, i, x) for(int i = (s); i <(x); i++)
#define int long long
template<typename A, typename B, typename C>
struct triple
{
	A X;
	B Y;
	C Z;
	triple(A a = 0, B b = 0, C c = 0) :X(a), Y(b), Z(c) {}
};
template<typename A, typename B, typename C>
triple<A, B, C> make_triple(A a = 0, B b = 0, C c = 0)
{
	return triple<A, B, C>(a, b, c);
}
template<typename A, typename B, typename C>
bool operator<(const triple<A, B, C>& a, const triple<A, B, C>& b)
{
	if (a.X != b.X)
		return a.X < b.X;
	if (a.Y != b.Y)
		return a.Y < b.Y;
	return a.Z < b.Z;
}
template<typename T, typename SS>
ostream& operator<<(ostream& ofs, const pair<T, SS>& p)
{
	ofs << "( " << p.F << " , " << p.S << " )";
	return ofs;
}
template<typename T>
void print(T a)
{
	for (auto i : a)
		cout << i << ' ';
	cout << '\n';
}
template<typename T>
T max(T a, T b, T c)
{
	return max(a, max(b, c));
}
template<typename T>
T min(T a, T b, T c)
{
	return min(a, min(b, c));
}
struct custom_hash
{
	static uint64_t splitmix64(uint64_t x)
	{
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	size_t operator()(uint64_t x) const
	{
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};
int sz, flx, fly, d, s, d1, d2;
int n;
int m;
#define mxn (int)(1e5 + 11)
int X1[mxn], Y1[mxn], X2[mxn], Y2[mxn];
inline int sum1(int x, int y, int k)
{
	y--, x--;
	sz = k * k;
	flx = (x + 1) / k;
	fly = (y + 1) / k;
	int ans = fly / 2 * sz * flx;
	if (fly & 1)
	{
		ans += flx / 2 * sz;
		if (flx & 1)
			ans += sz;
	}
	if ((x + 1) % k)
	{
		d = (x + 1) % k;
		s = (flx + 1) & 1;
		ans += fly / 2 * k * d;
		if (fly & 1 && s)
			ans += k * d;
	}
	if ((y + 1) % k != 0)
	{
		d = (y + 1) % k;
		s = (fly + 1) & 1;
		ans += flx / 2 * k * d;
		if (flx & 1 && s)
			ans += k * d;
	}
	if ((x + 1) % k && (y + 1) % k)
	{
		d1 = (x + 1) % k;
		d2 = (y + 1) % k;
		s = (fly + flx) & 1;
		s ^= 1;
		if (s)
			ans += d1 * d2;
	}
	return ans;
}
inline int sum(int x, int y, int t, int k)
{
	if (t)
		return sum1(x, y, k);
	else
		return x * y - sum1(x, y, k);
}
inline int sumr(int x1, int y1, int x2, int y2, int t, int k)
{
	if (x1 == x2 && y1 == y2)
	{
		int x = x1 / k - 1;
		int y = y1 / k - 1;
		if (x1 % k)
			x++;
		if (y1 % k)
			y++;
		if (!t)
			return (x + y) & 1;
		else
			return (x + y + 1) & 1;
	}
	return sum(x2, y2, t, k) - (x1 > 1 ? sum(x1 - 1, y2, t, k) : 0) - (y1 > 1 ? sum(x2, y1 - 1, t, k) : 0) + (x1 > 1 && y1 > 1 ? sum(x1 - 1, y1 - 1, t, k) : 0);
}
inline int solve(int k, int t)
{
	int ans = 0;
	int cntb = 0;
	int cntw = 0;
	for(int i =0; i < m; i++)
	{
		int r = sumr(X1[i], Y1[i], X2[i], Y2[i], t, k);
		cntb += r;
		cntw += (Y2[i] - Y1[i] + 1) * (X2[i] - X1[i] + 1) - r;
	}
	int allb = sumr(1, 1, n, n, t, k);
	cntw += allb - cntb;
	return cntw;
}
signed main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	srand(time(NULL));
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
	/*rng(20)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		cout << sumr(a, b, c, d, 0, 3) << '\n';
	}*/
	scanf("%d%d", &n, &m);
	for (int i =0; i <m ;i++)
		scanf("%d%d%d%d", &Y1[i], &X1[i], &Y2[i], &X2[i]);
	int ans = min(solve(1, 0), solve(1,1));
	for (int d = 2; d * d <= n; d++)
		if (n % d == 0)
		{
			ans = min(ans, solve(d, 0), solve(d, 1));
			ans = min(ans, solve(n/d, 0), solve(n/d, 1));
		}

	cout << ans << '\n';
}

Compilation message (stderr)

chessboard.cpp: In function 'long long int solve(long long int, long long int)':
chessboard.cpp:187:6: warning: unused variable 'ans' [-Wunused-variable]
  int ans = 0;
      ^~~
chessboard.cpp: In function 'int main()':
chessboard.cpp:214:22: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  scanf("%d%d", &n, &m);
                ~~    ^
chessboard.cpp:214:22: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
chessboard.cpp:216:51: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   scanf("%d%d%d%d", &Y1[i], &X1[i], &Y2[i], &X2[i]);
                     ~~~~~~                        ^
chessboard.cpp:216:51: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
chessboard.cpp:216:51: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
chessboard.cpp:216:51: warning: format '%d' expects argument of type 'int*', but argument 5 has type 'long long int*' [-Wformat=]
chessboard.cpp:214:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
chessboard.cpp:216:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &Y1[i], &X1[i], &Y2[i], &X2[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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