Submission #100472

#	Time	Username	Problem	Language	Result	Execution time	Memory
100472		davitmarg	Chessboard (IZhO18_chessboard)	C++17	100 / 100	722 ms	6776 KiB

chessboard

/*
DEATH-MATCH
Davit-Marg
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>  
#include <fstream>  
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
using namespace std;

LL n, k, best = mod * mod;
pair<LL, LL> c1[100005], c2[100005];
vector<LL> d;

LL check(LL d)
{
	LL r = (n*n) / (d*d) / 2 * (d*d);
	if (((n*n) / (d*d)) % 2 == 1)
		r += d * d;

	vector<int> prk(n+5,0), prz(n + 5,0);
	for (int i = 1; i <= n; i++)
	{
		prk[i] = prk[i - 1];
		if (((i-1) / d) % 2 == 0)
			prk[i]++;
		prz[i] = i - prk[i];
	}


	for (LL i = 0; i < k; i++)
	{
		LL zx = prz[c2[i].first] - prz[c1[i].first - 1], zy = prz[c2[i].second] - prz[c1[i].second - 1];
		LL kx = prk[c2[i].first] - prk[c1[i].first - 1], ky = prk[c2[i].second] - prk[c1[i].second - 1];
		r -= zx * zy;
		r -= kx * ky;
		r += kx * zy;
		r += zx * ky;
	}
	return r;
}

int main()
{
	cin >> n >> k;
	for (LL i = 1; i <= n / 2; i++)
		if (n%i == 0)
			d.PB(i);
	for (LL i = 0; i < k; i++)
	{
		cin >> c1[i].first >> c1[i].second >> c2[i].first >> c2[i].second;
	}

	for (LL i = 0; i < d.size(); i++)
	{
		LL ans = check(d[i]);
		best = min(best, min(n*n - ans, ans));
	}

	cout << best << endl;
	return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (LL i = 0; i < d.size(); i++)
                 ~~^~~~~~~~~~

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