Submission #670073

#	Time	Username	Problem	Language	Result	Execution time	Memory
670073		Kaztaev_Alisher	Chessboard (IZhO18_chessboard)	C++17	39 / 100	70 ms	3508 KiB

chessboard

//#pragma GCC optomize ("Ofast")
//#pragma GCC optomize ("unroll-loops")
//#pragma GCC target ("avx,avx2,fma")

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define sz size
#define cl clear
#define ins insert
#define ers erase
#define pii pair < int , int >
#define pll pair< long long  , long long >
#define all(x) x.begin() , x.end()
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define tostr(x) to_string(x)
#define tonum(s) atoi(s.c_str())
#define seon(x) setprecision(x)
#define bpop(x) __builtin_popcount(x)
#define deb(x) cerr << #x  << " = " << x << endl;
#define int ll

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
const double PI = 3.14159265;

const ll N = 1e5+5;
const ll mod = 1e9+7;
const ll inf = 1e9;
const ll INF = 1e18;

using namespace std;

struct {
	int x1,y1,x2,y2;
}t[N];

pair<int,int> get(int l,  int r , int len) {
	l --;
	r --;
	int sz = r-l+1;
	int ev = 0;
	int nxl = l/len*len+len;
	if(l/len%2 == 0) ev += min(r+1, nxl) - l;
	l = nxl;
	if(l > r) return {ev, sz-ev};
	
	int pdr = r/len*len-1;
	if(r/len%2 == 0) {
		ev += r-max(pdr,l-1);
	}
	r = pdr;
	if(l > r) return {ev, sz-ev};
	
	if(l/len%2 != r/len%2) {
		ev += (r-l+1)/2;
	}
	else {
		ev += ((r-l+1)/len+(l/len%2==0))/2*len;
	}
	return {ev, sz-ev};
}

void solve(){
//	int l, r,k1;
//	cin>>l>>r>>k1;
//	cout << get(l,r,k1).F << ' ' << get(l,r,k1).S;
//	return;
	int n , k;
	cin>> n >> k;
	int bs = 0;
	for(int i = 1; i <= k; i ++) {
		cin >> t[i].x1 >> t[i].y1 >> t[i].x2 >> t[i].y2;
		bs += (t[i].x2-t[i].x1+1)*(t[i].y2-t[i].y1+1);
	}
	vector<int> dels;
	for(int i = 1; i*i <= n; i ++) {
		if(n%i == 0) {
			dels.push_back(i);
			if(n/i != i && i > 1) dels.push_back(n/i);
		}
	}
	sort(all(dels));
	int ans = inf;
	for(auto len: dels) {
		int m = n/len;
		int ob = (m*m - (m*m/2)) * len*len;
		
		int rb = 0;
		int ww = 0;
		for(int i = 1; i <= k; i ++) {
			pair<int,int> X = get(t[i].x1, t[i].x2, len);
			pair<int,int> Y = get(t[i].y1, t[i].y2, len);
			rb += X.F * Y.F;
			rb += X.S * Y.S;
			ww += X.F * Y.S;
			ww += X.S * Y.F;
		}
//		cout << len << ' ' << rb << ' ' << ww << '\n';
//		cout << "ob: " << ob << '\n';
//		cout << "posss " << ww + (ob-rb) << ' ' << rb + (n*n-ob-ww) << '\n';
		ans = min(ans, ww + (ob-rb));
		ans = min(ans, rb + (n*n-ob-ww));
	}
	cout << ans;
}
signed main(){
	ios;
	int t = 1;
//	cin >> t;
	while(t--) solve();
	return 0;
}
/*
*/

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