Submission #379024

#	Time	Username	Problem	Language	Result	Execution time	Memory
379024		fhvirus	Chessboard (IZhO18_chessboard)	C++17	70 / 100	2060 ms	492 KiB

chessboard

// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii; typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define FOR(i,n) for(int i = 0; i < (n); ++i)
#define FOO(i,a,b) for(int i = (a); i <= (b); ++i)
#define AI(x) begin(x),end(x)
template<class I> bool chmax(I &a, I b){ return a < b ? (a = b, true) : false;}
template<class I> bool chmin(I &a, I b){ return a > b ? (a = b, true) : false;}
#ifdef OWO
#define debug(args...) LKJ("[ " + string(#args) + " ]", args)
void LKJ(){ cerr << endl;}
template<class I, class...T> void LKJ(I&&x, T&&...t){ cerr<<x<<", ", LKJ(t...);}
template<class I> void DE(I a, I b){ while(a < b) cerr << *a << " \n"[next(a) == b], ++a;}
#else
#define debug(...) 0
#define DE(...) 0
#endif
const int N = 1e5 + 1;
int n, k;

void findfac(int n, vector<int> &fac){
	for(int i = 1; i * i <= n; ++i){
		if(n % i != 0) continue;
		fac.pb(i);
		fac.pb(n / i);
	}
	sort(AI(fac));
	fac.erase(unique(AI(fac)), end(fac));
	if(fac.back() == n) fac.pop_back();
}

ll calc(int l, int r, int f){
	ll ans = 0;
	int odd = ((l / f) & 1);
	FOO(x, l, r){
		if(((x / f) & 1) != odd) --ans;
		else ++ans;
	}
	return ans;
}

int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> k;

	vector<int> facs;
	findfac(n, facs);

	// ca : has top left corner
	// cb : does not
	vector<ll> ca(facs.size());
	vector<ll> cb(facs.size());
	FOR(i,facs.size()){
		int f = facs[i];
		ll nn = n / f;
		ll bc = (nn * nn + 1) / 2;
		ca[i] = bc * f * f;
		cb[i] = 1ll * n * n - ca[i];
	}

	FOR(_,k){
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		--x1, --y1, --x2, --y2;
		FOR(i, facs.size()){
			int f = facs[i];
			int lx = (x2 - x1 + 1);
			int ly = (y2 - y1 + 1);
			lx %= f * 2, ly %= f * 2;
			if(lx == 0 or ly == 0) continue;
			int xr = x1 + lx - 1, yr = y1 + ly - 1;

			ll vx = calc(x1, x2, f);
			ll vy = calc(y1, y2, f);

			if((x1 / f) + (y1 / f) & 1) vx *= 1;
			else vx *= -1;

			ca[i] += vx * vy;
			cb[i] -= vx * vy;
		}
	}

	DE(AI(facs));
	DE(AI(ca));
	DE(AI(cb));

	cout << min(
		*min_element(AI(ca)),
		*min_element(AI(cb))
	);
	return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'int32_t main()':
chessboard.cpp:9:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,n) for(int i = 0; i < (n); ++i)
      |                                   ^
chessboard.cpp:58:2: note: in expansion of macro 'FOR'
   58 |  FOR(i,facs.size()){
      |  ^~~
chessboard.cpp:9:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,n) for(int i = 0; i < (n); ++i)
      |                                   ^
chessboard.cpp:70:3: note: in expansion of macro 'FOR'
   70 |   FOR(i, facs.size()){
      |   ^~~
chessboard.cpp:81:16: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   81 |    if((x1 / f) + (y1 / f) & 1) vx *= 1;
      |       ~~~~~~~~~^~~~~~~~~~
chessboard.cpp:76:8: warning: unused variable 'xr' [-Wunused-variable]
   76 |    int xr = x1 + lx - 1, yr = y1 + ly - 1;
      |        ^~
chessboard.cpp:76:26: warning: unused variable 'yr' [-Wunused-variable]
   76 |    int xr = x1 + lx - 1, yr = y1 + ly - 1;
      |                          ^~
chessboard.cpp:21:17: warning: statement has no effect [-Wunused-value]
   21 | #define DE(...) 0
      |                 ^
chessboard.cpp:89:2: note: in expansion of macro 'DE'
   89 |  DE(AI(facs));
      |  ^~
chessboard.cpp:21:17: warning: statement has no effect [-Wunused-value]
   21 | #define DE(...) 0
      |                 ^
chessboard.cpp:90:2: note: in expansion of macro 'DE'
   90 |  DE(AI(ca));
      |  ^~
chessboard.cpp:21:17: warning: statement has no effect [-Wunused-value]
   21 | #define DE(...) 0
      |                 ^
chessboard.cpp:91:2: note: in expansion of macro 'DE'
   91 |  DE(AI(cb));
      |  ^~

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