Submission #40363

#	Time	Username	Problem	Language	Result	Execution time	Memory
40363		model_code	Chessboard (IZhO18_chessboard)	C++11	100 / 100	1200 ms	2292 KiB

chessboard

//Solution by Tima
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
#include <map>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <bitset>
#define f first
#define s second
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define pb push_back
#define vi vector <int>
#define ld long double
#define pii pair<int, int>
#define y1 sda
using namespace std;    
const int N = int(3e5), mod = int(1e9)  + 7; 

int n, k, x1[N], y1[N], x2[N], y2[N];
ll ans;
int pos;

inline ll gety(ll y,ll len){
	if(y <= 0) return 0;
	ll res = (y / len) / 2 * len;
	if((y / len) & 1) res += y % len + 1;
	return res;
}

inline ll getx(ll x,ll len){
	if(x <= 0) return 0;
	ll res = (x / len) / 2 * len;
	if((x / len) & 1) res += x % len + 1;
	return res;
}

void solve(int len){
	ll odd = 0, even = 0;
	for(int i = 1,xx,yy; i <= k; i++){
		ll o1 = gety(y2[i], len) - gety(y1[i] - 1, len);
		ll e1 = (y2[i] - y1[i] + 1) - o1;
		ll o2 = getx(x2[i], len) -  getx(x1[i] - 1, len); 
		ll e2 = (x2[i] - x1[i] + 1) - o2;
		xx = x1[i] / len;
		yy = y1[i] / len;
		if(xx & 1) swap(o1,e1);
		if(yy & 1) swap(o2,e2);
		ll od = 0, ev = 0;
		if((xx + yy) & 1){
			od = e1 * e2 + o1 * o2;
		}
		else{
		    od = o1 * e2 + e1 * o2;
		}
		ev = 1ll * (x2[i] - x1[i] + 1) * (y2[i] - y1[i] + 1) - od;
		
		odd += od;
		even += ev;
	}
	ll cnt = 1ll * (n / len) * (n / len);
	ll res = min(cnt / 2 * len * len + even - odd, (cnt + 1) / 2 * len * len + odd - even);
	if(res < ans){
	    pos = len;
		ans = res;
	}
}

int main () {
	ans = (ll)(1e18);
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= k; i++){
		scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]);
		x1[i]--,y1[i]--,x2[i]--,y2[i]--;
	}
	for(int i = 1; i * i <= n; i++){
		if(n % i == 0){
			solve(i);
			if(i > 1) solve(n / i);
		}
	}
	printf("%lld", ans);


return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:81:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
                       ^
chessboard.cpp:83:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[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