Submission #81962

#	Time	Username	Problem	Language	Result	Execution time	Memory
81962		Good	Chessboard (IZhO18_chessboard)	C++11	100 / 100	812 ms	6404 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;

bool calc (int x, int y, int z) {
	x --, y --;
	return ((x / z) % 2) ^ ((y / z) % 2);
}


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);

	for (auto j: A) {
		ll v = j;
		ll u = n / j;
		
		ll sm1[2], sm2[2];
		sm1[0] = sm2[1] = 0;
		
		sm1[1] = (((u * u) + 1) / 2) * v * v;
		sm2[0] = ((u * u) / 2) * v * v;
																
		for (int i = 1; i <= k; i++) {
			ll a = min ((j - (x[i].ff - 1) % j) % j, x[i].ss - x[i].ff + 1);
			ll b = x[i].ss % j;
			ll c = min ((j - (y[i].ff - 1) % j) % j, y[i].ss - y[i].ff + 1);
			ll d = y[i].ss % j;
			
			if (x[i].ff + a > x[i].ss)
				b = 0;
			if (y[i].ff + c > y[i].ss)
				d = 0;	
						
			bool e = calc (x[i].ff, y[i].ff, j);
			sm1[e] += a * c, sm2[e] += a * c;
			
			e = calc (x[i].ff, y[i].ff + c, j);
			ll t = (y[i].ss - y[i].ff - c + 1) / j;
			ll r = (t + 1) / 2 * a * j;
			sm1[e] += r, sm2[e] += r;
			r = t / 2 * a * j;
			sm1[!e] += r, sm2[!e] += r;
			
			e = calc (x[i].ff, y[i].ss, j);
			sm1[e] += a * d, sm2[e] += a * d;
						
			ll xx1 = x[i].ff + a;
			if (xx1 > x[i].ss)
				continue;
			
			e = calc (x[i].ss, y[i].ff, j);
			sm1[e] += b * c, sm2[e] += b * c;
			
			e = calc (x[i].ss, y[i].ff + c, j);
			r = (t + 1) / 2 * b * j;
			sm1[e] += r, sm2[e] += r;
			r = t / 2 * b * j;
			sm1[!e] += r, sm2[!e] += r;
			
			e = calc (x[i].ss, y[i].ss, j);
			sm1[e] += b * d, sm2[e] += b * d;			
			
			ll xx2 = x[i].ss - b;
			if (xx1 > xx2)
				continue;
			
			e = calc (xx1, y[i].ff, j);
			t = (xx2 - xx1 + 1) / j;
			r = (t + 1) / 2 * c * j;
			sm1[e] += r, sm2[e] += r;
			r = t / 2 * c * j;
			sm1[!e] += r, sm2[!e] += r;
			
			ll yy1 = y[i].ff + c;
			if (yy1 > y[i].ss)
				continue;
			
			e = calc (xx1, y[i].ss, j);
			r = (t + 1) / 2 * d * j;
			sm1[e] += r, sm2[e] += r;
			r = t / 2 * d * j;
			sm1[!e] += r, sm2[!e] += r;
			
			ll yy2 = y[i].ss - d;
			if (yy1 > yy2)
				continue;
									
			e = calc (xx1, yy1, j);
			t = (yy2 - yy1 + 1) / j;
			ll t1 = (xx2 - xx1 + 1) / j;
			r = (((t + 1) / 2) * ((t1 + 1) / 2) + (t / 2) * (t1 / 2)) * j * j;
			sm1[e] += r, sm2[e] += r;
			r = ((t / 2) * ((t1 + 1) / 2) + ((t + 1) / 2) * (t1 / 2)) * j * j;
			sm1[!e] += r, sm2[!e] += r;
		}
		
		ans = min (ans, min (sm1[1] - sm1[0], sm2[0] - sm2[1]));
	}	

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

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:40: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:43: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: 30 / 30