Submission #76739

#	Time	Username	Problem	Language	Result	Execution time	Memory
76739		Good	Chessboard (IZhO18_chessboard)	C++11	70 / 100	2055 ms	63724 KiB

chessboard

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define ff first
#define ss second
#define Maxn 100009
#define ll long long
#define pb push_back
#define Inf 1000000009
#define ppb() pop_back()
#define pii pair <int , int>
#define mid(x, y) (x + y) / 2
#define all(x) x.begin(),x.end()
#define llInf 1000000000000000009
#define tr(i, c) for(__typeof(c).begin() i = (c).begin() ; i != (c).end() ; i++)
using namespace std;
using namespace __gnu_pbds;
typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> order;

int n, k;
pii x[Maxn];
pii y[Maxn];
ll ans = llInf;

vector <int> A;

int main () {
	//freopen ("file.in", "r", stdin);
	//freopen ("file.out", "w", stdout);
	
 	//srand ((unsigned) time ( NULL ));
	//int randomNumber = rand() % 10 + 1;

	scanf ("%d%d", &n, &k);

	for (int i = 1; i <= k; i++)
		scanf ("%d%d%d%d", &x[i].ff, &y[i].ff, &x[i].ss, &y[i].ss);	


	for (int i = 1; i < n; i++)
		if (!(n % i))
			A.pb (i);	

	if (k == 0) {
		for (auto i: A) {
			ll v = i;
			ll u = n / i;
			
			u = ((u * u) / 2) * v * v;
			ans = min (ans, u);
		}
		
		return printf ("%lld\n", ans), 0;	
	}

	for (int i = 0; i < 2; i++) {
		for (auto j: A) {
			ll v = j;
			ll u = n / j;
			
			if (i)
				u = ((u * u) / 2) * v * v;
			
			else
				u = ((u * u) - (u * u) / 2) * v * v;
						
			for (int l = 1; l <= k; l++) {
				for (int p = x[l].ff; p <= x[l].ss; p++)
					for (int e = y[l].ff; e <= y[l].ss; e++) {
						int a = (p - 1) / j;
						int b = (e - 1) / j;
						
						bool q = 0;
						if (!(a & 1) and b & 1) q = 1;
						if (a & 1 and !(b & 1)) q = 1;
							
						if (i)
							q = !q;							
						
						if (q) u++;
						else u --;
															
					}	 
			}
			ans = min (ans, u);
		}	
	}

	printf ("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &n, &k);
  ~~~~~~^~~~~~~~~~~~~~~~
chessboard.cpp:37:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d%d%d", &x[i].ff, &y[i].ff, &x[i].ss, &y[i].ss); 
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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