Submission #857282

#	Time	Username	Problem	Language	Result	Execution time	Memory
857282		NaimSS	Chessboard (IZhO18_chessboard)	C++14	16 / 100	30 ms	5324 KiB

chessboard

#include <bits/stdc++.h>
#include <iostream>
// #define int long long
#define ld long double
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define Unique(v) sort(all(v)),v.erase(unique(all(v)),v.end());
#define sz(v) ((int)v.size())
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
//#define left oooooopss
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
#define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
// std::mt19937_64 rng64((int) std::chrono::steady_clock::now().time_since_epoch().count());
std::mt19937 rng(
  
//  (int) std::chrono::steady_clock::now().time_since_epoch().count()
   1239010
);
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
//inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll b,ll e,ll m){
    b%=m;
    ll ans = 1;
    for (; e; b = b * b % m, e /= 2)
        if (e & 1) ans = ans * b % m;
    return ans;
}
// debug:
template<class T>void print_vector(vector<T> &v){
    rep(i,0,sz(v))cout<<v[i]<<" \n"[i==sz(v)-1];
}
void dbg_out() {cerr << endl; }
template<typename Head, typename ... Tail> void dbg_out(Head H,Tail... T){
    cerr << ' ' << H;
    dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__), cerr << endl
#else
#define dbg(...) 42
#endif
//
const int N = 100100;
ll x[N][2] , y[N][2];
int n,k;
ll solve(int d,int ini){
	ll L = n / d;
	ll totW = (L * L + 1)/2 * d * d;
	ll totB = (L*L)/2 * d * d;
	if(ini==1)swap(totW,totB);
	ll res = totB;
	auto add = [&](ll totW,ll totB,int inic){
		if(inic)swap(totW,totB);
		res -= totB;
		res += totW;
		return ;
	};
	rep(i,0,k){
		pll p1;
		if(x[i][0] % d != 0){
			p1.ff = x[i][0] + (d - x[i][0]);
		}else p1.ff = x[i][0];
		p1.ss = y[i][0] + (y[i][0]%d==0 ? 0 : d - (y[i][0]%d));
		pll p2;
		p2.ff = x[i][1] - (x[i][1]%d == d-1 ? 0 : (x[i][1]%d) + 1);
		p2.ss = y[i][1] - (y[i][1]%d == d-1 ? 0 : (y[i][1]%d) + 1);
		
		if(p1.ff <= p2.ff && p1.ss <= p2.ss){
			// all inside:
			ll l = (p2.ff - p1.ff + 1)/d;
			ll h = (p2.ss - p1.ss + 1)/d;
			int inic =(((p1.ff/d)+(p1.ss/d)) &1)^ini;
			ll totW = (l*h + 1)/2 * d * d;
			ll totB = (l*h)/2 * d * d;
			dbg(totW,totB);
			add(totW,totB,inic);
		}
		// upper:
		if(x[i][0] <= p1.ff - 1){
			int inic =(((x[i][0]/d)+(y[i][0]/d)) &1)^ini;
			ll l = (y[i][1] - y[i][0] + 1);
			ll h = (p1.ff-1 - x[i][0] + 1);
			ll totW = (l*h +1)/2;
			ll totB = (l*h)/2;
			add(totW,totB,inic);
		}
		// lower
		if(p2.ff + 1 <= x[i][1]){
			int inic = (((x[i][1]/d) + (y[i][1]/d))&1)^ini;
			ll l = (y[i][1] - y[i][0] + 1);
			ll h = (x[i][1] - (p2.ff + 1) + 1);
			ll totW = (l*h +1)/2;
			ll totB = (l*h)/2;
			add(totW,totB,inic);
		}
		// left:
		pll P1 = pll(p1.ff,y[i][0]), P2 = pll(p2.ff-1, p1.ss-1);
		if(P1.ff <= P2.ff && P1.ss <= P2.ss){
			int inic = ((P1.ff/d + P2.ff/d)& 1)^ini;
			ll l = P2.ff - P1.ff + 1;
			ll h = P2.ss - P1.ss + 1;
			ll totW = (l*h + 1)/2;
			ll totB = l*h/2;
			add(totW,totB,inic);
		}
		// right:
		P1 = pll(p2.ff, p2.ss + 1), P2 = pll(p2.ff-1,y[i][1]);
		if(P1.ff <= P2.ff && P1.ss <= P2.ss){
			int inic = ((P1.ff/d + P2.ff/d)& 1)^ini;
			ll l = P2.ff - P1.ff + 1;
			ll h = P2.ss - P1.ss + 1;
			ll totW = (l*h + 1)/2;
			ll totB = l*h/2;
			add(totW,totB,inic);
		}
	}
	dbg(d, ini , res);
	
	return res;
}

int32_t main(){
    fastio;
	cin >> n >> k;
	rep(i,0,k){
		rep(j,0,2)cin >> x[i][j] >> y[i][j];
	}
	ll res = n * (ll) n;
	for(int d=1;d < n;d++){
		if(n%d == 0){
			res = min(res, solve(d,0));
			res = min(res, solve(d,1));
		}
	}
	cout << res << endl;
	// math -> gcd it all
    // Did you swap N,M? N=1?
}

Compilation message (stderr)

chessboard.cpp: In function 'll solve(int, int)':
chessboard.cpp:58:18: warning: statement has no effect [-Wunused-value]
   58 | #define dbg(...) 42
      |                  ^~
chessboard.cpp:93:4: note: in expansion of macro 'dbg'
   93 |    dbg(totW,totB);
      |    ^~~
chessboard.cpp:58:18: warning: statement has no effect [-Wunused-value]
   58 | #define dbg(...) 42
      |                  ^~
chessboard.cpp:135:2: note: in expansion of macro 'dbg'
  135 |  dbg(d, ini , res);
      |  ^~~

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