Submission #92988

#	Time	Username	Problem	Language	Result	Execution time	Memory
92988		Moysenko	Chessboard (IZhO18_chessboard)	C++17	70 / 100	120 ms	3548 KiB

chessboard

/*ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГИ░░ 
▄███▀░◐░░░▌░░░░░░░ 
░░░░▌░░░░░▐░░░░░░░ 
░░░░▐░░░░░▐░░░░░░░ 
░░░░▌░░░░░▐▄▄░░░░░ 
░░░░▌░░░░▄▀▒▒▀▀▀▀▄ 
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄ 
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄ 
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄ 
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄ 
░░░░░░░░░░░▌▌░▌▌░░░░░ 
░░░░░░░░░░░▌▌░▌▌░░░░░ 
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
НАСТРОЙКА НА КРИТЫ ██████████████] 100% СОЧНОСТИ*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <queue>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <chrono>
#include <ctime>
#include <unordered_set>
#include <random>
  
#define ep emplace_back
#define F first
#define S second
  
using namespace std;
  
typedef long long ll;
typedef long double ld;
const int inf = 1e9 + 7;
mt19937 rd(chrono :: system_clock :: now().time_since_epoch().count());
  
#pragma GCC optimize("unroll-loops") // развернуть цикл
#pragma GCC optimize("Ofast") // скомпилировать с о3
/*
#pragma GCC optimize("no-stack-protector") // что-то со стеком
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native") // оптимизации процессора
#pragma GCC optimize("fast-math") // оптимизации сопроцессора
*/

const int siz = 1e5 + 10;
int K, x[siz], y[siz];
ll n;

ll Solve(int l){
	ll k1 = (n / l + 1) / 2, k2 = (n / l) / 2;
	ll all = k1 * k1 + k2 * k2;
	all *= (ll)l * l;

	int ox, oy;
	for (int i = 0; i < K; i++){
		ox = x[i] % (2 * l);
		oy = y[i] % (2 * l);

		if (!((ox < l) ^ (oy < l)))
			all--;
		else
			all++;
	}

	//cout << l << ' ' << all << '\n';

	return min(all, n * n - all);
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    cin >> n >> K;
    int i, tx, ty;
   	for (i = 0; i < K; i++){
   		cin >> x[i] >> y[i] >> tx >> ty;
   		if (x[i] != tx || y[i] != ty){
   			cout << 8;
   			return 0;
   		}
   		x[i]--, y[i]--;
   	}

   	ll ans = Solve(1);
   	for (i = 2; i * i <= n; i++)
   		if (n % i == 0)
   			ans = min(ans, min(Solve(i), Solve(n / i)));

   	cout << ans;
}	

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