제출 #378866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378866		hhhhaura	Chessboard (IZhO18_chessboard)	C++14	100 / 100	620 ms	5868 KiB

chessboard

#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define ceil(a, b) ((a + b - 1) / (b))
#define all(x) x.begin(), x.end()

#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)
#define MAXN 1000005

#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

using namespace std;
#ifdef wiwihorz
#define print(a...) kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) {
	while(L < R) cerr << *L << " \n"[next(L) == R], ++ L;
}
void kout() {cerr << endl;}
template<class T1, class ... T2> void kout(T1 a, T2 ... e) {
	cerr << a << " ", kout(e...);
}
#else 
#define print(...) 0
#define vprint(...) 0
#endif
struct sb2 {
	int n, k;
	struct pt {
		int u, l, d, r;
	};
	vector<pt> a;
	void init_(int _n, int _k) {
		n = _n, k = _k;
		a.assign(k + 1, {0, 0, 0, 0});
	}
	int solve() {
		int ans[2];
		ans[0] = ans[1] = 0;
		rep(i, 1, k) {
			int x, y;
			x = a[i].u, y = a[i].l;
			if((x & 1) == (y & 1)) ans[0] ++;
			else ans[1] ++;
		}
		int cnt1 = ceil(n, 2) * ceil(n, 2) + (n / 2) * (n / 2);
		int aa = cnt1 - ans[0] + ans[1];
		int bb = n * n - cnt1 - ans[1] + ans[0];
		return min(aa, bb);
	}

} ;
struct sb1 {
	int n, k;
	struct pt {
		int u, l, d, r;
	};
	vector<pt> a;
	void init_(int _n, int _k) {
		n = _n, k = _k;
		a.assign(k + 1, {0, 0, 0, 0});
	}
	int solve() {
		int ans = INF;
		rep(i, 1, n - 1) {
			if(n % i) continue;
			int cnt = 0;
			rep(j, 1, n / i) rep(m, 1, n / i) {
				cnt += i * i * bool((j & 1) == (m & 1));
			}
			ans = min(ans, n * n - cnt);
		}
		return ans;
	}

} ;
struct sb3 {
	int n, k;
	struct pt {
		int u, l, d, r;
	};
	vector<pt> a;
	void init_(int _n, int _k) {
		n = _n, k = _k;
		a.assign(k + 1, {0, 0, 0, 0});
	}
	int get(int x) {
		return ceil(x, 2) * ceil(x, 2) + (x / 2) * (x / 2);
	}
	int cal(int x) {
		assert(n % x == 0);
		int ans[2]; ans[0] = 0, ans[1] = 0;
		rep(i, 1, k) {
			int u = a[i].u, l = a[i].l;
			int uu = ceil(u, x) & 1, ll = ceil(l, x) & 1;
			ans[(uu == ll)] ++;
		}
		int cc = get(n / x);
		int cnt1 = x * x * cc + ans[0] - ans[1];
		int cnt2 = ((n / x) * (n / x) - cc) * x * x + ans[1] - ans[0];
		print(x, cnt1, cnt2, ans[0], ans[1]);
		return min(cnt1, cnt2);
	}
	int solve() {
		int kk = sqrt(n) + 1, ans = INF;
		rep(i, 1, kk) {
			if(n % i) continue;
			if(i != n) ans = min(ans, cal(i));
			if(n / i != n)ans = min(ans, cal(n / i));
		}
		return ans;
	}

} ;
struct sb4 {
	int n, k;
	struct pt {
		int u, l, d, r;
	};
	vector<pt> a;
	void init_(int _n, int _k) {
		n = _n, k = _k;
		a.assign(k + 1, {0, 0, 0, 0});
	}
	int get(int x) {
		return ceil(x, 2) * ceil(x, 2) + (x / 2) * (x / 2);
	}
	int pre(int x, int y, int v) {
		int ans = 0, xx = ceil(x, v) - 1, yy = ceil(y, v) - 1;
		if(x == 0 || y == 0) return 0;
		ans += ceil(xx, 2) * ceil(yy, 2) * v * v + (xx / 2) * (yy / 2) * v * v;
		// down
		if(xx & 1) ans += (yy / 2) * (x - xx * v) * v;
		else ans += ceil(yy , 2) * (x - xx * v) * v;
		// right
		if(yy & 1) ans += (xx / 2) * (y - yy * v) * v;
		else ans += ceil(xx, 2) * (y - yy * v) * v;
		// r0d
		if((xx & 1) == (yy & 1)) ans += (x - xx * v) * (y - yy * v);

		return ans;
	} 
	int val(int u, int d, int l, int r, int v) {
		int ans = pre(d, r, v) - pre(d, l - 1, v) 
			- pre(u - 1, r, v) + pre(u - 1, l - 1, v);
//		print(u, d, l, r, v, ans);
		return ans;
	}
	int cal(int x) {
		assert(n % x == 0);
		int ans[2]; ans[0] = 0, ans[1] = 0;
		rep(i, 1, k) {
			int u = a[i].u, l = a[i].l, d = a[i].d, r = a[i].r;
			int area = (d - u + 1) * (r - l + 1);
			ans[1] += val(u, d, l, r, x);
			ans[0] += area - val(u, d, l, r, x);
		}
		int cc = get(n / x);
		int cnt1 = x * x * cc + ans[0] - ans[1];
		int cnt2 = ((n / x) * (n / x) - cc) * x * x + ans[1] - ans[0];
		return min(cnt1, cnt2);
	}
	int solve() {
		int kk = sqrt(n) + 1, ans = INF;
		rep(i, 1, kk) {
			if(n % i) continue;
			if(i != n) ans = min(ans, cal(i));
			if(n / i != n)ans = min(ans, cal(n / i));
		}
		return ans;
	}

} ac;
int cal1(int u, int d, int l, int r, int v) {
	int ans = 0;
	rep(i, u, d) rep(j, l, r) {
		ans += bool((ceil(i, v) & 1) == (ceil(j, v) & 1));
	}
	return ans;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, k; cin >> n >> k;
	ac.init_(n, k);
	rep(i, 1, k) {
		cin >> ac.a[i].u >> ac.a[i].l;
		cin >> ac.a[i].d >> ac.a[i].r;
	}
	cout << ac.solve() << "\n";
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

chessboard.cpp:4: warning: ignoring #pragma loop  [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
chessboard.cpp:24:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   24 | void vprint(auto L, auto R) {
      |             ^~~~
chessboard.cpp:24:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   24 | void vprint(auto L, auto R) {
      |                     ^~~~

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