Submission #492397

#	Time	Username	Problem	Language	Result	Execution time	Memory
492397		hohohaha	Chessboard (IZhO18_chessboard)	C++14	100 / 100	322 ms	4576 KiB

chessboard

// #pragma GCC optimize("Ofast")
// #pragma GCC targt("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")

#include "bits/stdc++.h"

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>


#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front

#define fr front
#define bc back

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)

#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '

#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

void solve();

signed main() {
// freopen("output.out","w",stdout);
   fastio();
   
   int tc = 1;
   
//   cin >> tc; 
   
   fori(test, 1, tc) {
      solve();
   }
   return 0;
}

const ld pi = 4 * atan(1.0), eps = 1e-9;

#define int long long
const int maxn = 200000 + 5, mod = 924844033; 

const int inf = LLONG_MAX / 2; 

int n, m; 

int sum = 0; 

vector<pair<ii, ii> > al; 

int get(int i, int k) { 
//	cout << i << sp << min(i % (2 * k), k)<< sp << (i / (2 * k) * k) << endl;
	return min(i % (2 * k), k) + (i / (2 * k) * k); 
}

void solve() {
	cin >> n>> m; 
	fori(i,1 , m) {
		int a, b, c, d; 
		cin >> a >> b >> c >> d;
		al.eb(ii(a, b), ii(c, d)); 
	}
	int ans= inf; 
	fori(i, 1, n - 1) { 
		if(n % i == 0) {
			int blocks = n * n / (i * i); int black = (blocks + 1) / 2 * i * i;
//			cout << blocks << endl;
			int a1 = black, a2 = n * n - black; 
//			cout<< "a: " << a1 << sp << a2 << endl;
			for(auto t : al) {
				int a = t.fi.fi, b = t.fi.se, c = t.se.fi, d = t.se.se; 	
				
				int area = (c - a + 1) * (d- b + 1);
				
				int h = get(c, i) - get(a - 1, i), w = get(d, i) - get(b- 1, i); 
			 	
			 	int smblack = h * w + (c - a + 1 - h) * (d - b + 1 - w); 
			 	
//			 	cout << i << sp << h << sp << w << sp << smblack << endl;;
			 	
			 	a1 -= smblack; 
			 	a2 -= area - smblack;
				
				a1 += area - smblack; 
				a2 += smblack; 
//				cout << a1 << sp << a2 << ":::" << endl;
			}
			ans = min(ans, a1); 
			ans = min(ans, a2);
		}
	}
	cout << ans; 
}

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