제출 #1269237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269237		nub	Chessboard (IZhO18_chessboard)	C++20	100 / 100	465 ms	592 KiB

chessboard

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define ci const int
#define cll const long long
#define cull const unsigned long long
#define cd const double
#define cld const long double
#define fi first
#define se second
#define psb push_back
#define ppb pop_back
#define psf push_front
#define ppf pop_front
#define ps push
#define pp pop
using namespace std;

string file_name = "";
string input_extension = "";
string output_extension = "";

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){
	return uniform_int_distribution<ll>(l, r)(rng);
}

ci inf = 1e9;
ci neginf = -1e9;
cll inf_ll = 1e18;
cll neginf_ll = -1e18;

ll mulmod(ll a, ll b, ll MOD = LLONG_MAX){
	return ((a%MOD)*(b%MOD)%MOD+MOD)%MOD;
}

ll binpow(ll a, ll b, ll MOD = LLONG_MAX){
	ll res = 1, t = a % MOD, exp = b;
	while (exp > 0){
		if (exp & 1) res = mulmod(res, t, MOD);
		t = mulmod(t, t, MOD);
		exp >>= 1;
	}
	return res;
}

ll invmod(ll a, ll MOD = LLONG_MAX){
	return binpow(a, MOD-2, MOD);
}

/*
It's ok to not get all the subtasks
Think of each subtask as a separate problem
The goal is to get as many points as possible
Solve if you can think of a method instantly (even brute force)
If not, skip and return later
Always check your code on multiple test cases
Consider offline processing when online is too messy
Consider processing in reverse
(If you're doing codeforces, maybe try to OneShot it)

Notes:
READ THE PROBLEM STATEMENT CAREFULLY
Check for double counting / undercounting
Clear arrays between testcases
Clear and resize arrays before algorithm
(Try to) Set default values for everything
Double check vector / array sizes
Remember to sort when (mostly) doing greedy
Check for max / min inputs
Check for edge cases
Check for 0-index vs 1-index bugs
Check loop bounds, PLEASE

"Losing a ton of points or time for no reason" counter: 9
*/

// from (1, 1) to (x, y), count black squares with step (assuming top
ll calc_corner(ll x, ll y, ll step){
	if (x < 1 || y < 1) return 0;
	ll a = x/step, b = x%step, c = y/step, d = y%step;
	
	ll res = (a*c + 1) / 2 * step * step;
	if (a%2 == 0) res += b * ((c+1)/2) * step;
	else res += b * (c/2) * step;
	if (c%2 == 0) res += d * ((a+1)/2) * step;
	else res += d * (a/2) * step;
	if ((a+c)%2 == 0) res += b*d;
	
	return res;
}

ll calc_rect(ll u, ll l, ll d, ll r, ll step){
	ll res = 0;
	res += calc_corner(d, r, step);
	res -= calc_corner(u-1, r, step);
	res -= calc_corner(d, l-1, step);
	res += calc_corner(u-1, l-1, step);
	return res;
}

vector<ll> factor;
vector<ll> res;
ll n, m, k;
ll u, l, d, r, t;

void solve(){
	factor.clear();
	res.clear();
	
	cin >> n;
	for (int i=1; i<n; i++){
		if (n%i == 0) factor.psb(i);
	}
	m = factor.size();
	res.resize(m, 0);
	for (int i=0; i<m; i++){
		res[i] = calc_rect(1, 1, n, n, factor[i]);
	}
	
	cin >> k;
	while (k--){
		cin >> u >> l >> d >> r;
		for (int i=0; i<m; i++){
			t = calc_rect(u, l, d, r, factor[i]);
			res[i] -= t*2 - (d-u+1) * (r-l+1);
		}
	}
	
	ll ans = n*n;
	for (int i=0; i<m; i++){
		ans = min({ans, res[i], n*n-res[i]});
	}
	cout << ans;
}

int main(){
	if (file_name.size() > 0 && input_extension.size() > 0){
		freopen((file_name+input_extension).c_str(), "r", stdin);
	}
	if (file_name.size() > 0 && output_extension.size() > 0){
		freopen((file_name+output_extension).c_str(), "w", stdout);
	}
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int t=1;
//	cin >> t;
	while (t--) solve();
}

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

chessboard.cpp: In function 'int main()':
chessboard.cpp:140:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |                 freopen((file_name+input_extension).c_str(), "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
chessboard.cpp:143:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |                 freopen((file_name+output_extension).c_str(), "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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