Submission #50839

#	Time	Username	Problem	Language	Result	Execution time	Memory
50839		Nicksechko	Chessboard (IZhO18_chessboard)	C++14	0 / 100	41 ms	2408 KiB

chessboard

//Solution by Tima
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
#include <map>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <bitset>
#define f first
#define s second
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define pb push_back
#define vi vector <int>
#define ld long double
#define pii pair<int, int>
#define y1 sda
using namespace std;    
const int N = int(3e5), mod = int(1e9)  + 7; 

int n, k, x[N], y[N];
ll ans;
int pos;

void solve(int len){
	int c1 = 0, c2 = 0,xx,yy;
	for(int i = 1; i <= k; i++){
		xx = (x[i] + len - 1) / len;
		yy = (y[i] + len - 1) / len;
		if(abs(xx - yy) & 1) c2++;
		else c1++;
	}
	ll cnt = 1ll * (n / len) * (n / len);
	ll res = min(cnt / 2 * len * len - c2 + c1, (cnt + 1) / 2 * len * len - c1 + c2);
	if(res < ans){
		ans = res;
		pos = len;
	}
}

int main () {
	ans = (ll)(1e18);
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= k; i++){
		scanf("%d%d%d%d", &x[i], &y[i], &x[i], &y[i]);
	}

	for(int i = 1; i * i <= n; i++){
		if(n % i == 0){
			solve(i);
			if(i > 1) solve(n / i);
		}
	}
	cerr << "Len: " << pos << endl;

	printf("%lld", ans);


return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~
chessboard.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &x[i], &y[i], &x[i], &y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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