Submission #50839

# Submission time Handle Problem Language Result Execution time Memory
50839 2018-06-13T16:26:25 Z Nicksechko Chessboard (IZhO18_chessboard) C++14
0 / 100
41 ms 2408 KB
//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

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]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 2408 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2408 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2408 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 2408 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -