Submission #58848

#	Time	Username	Problem	Language	Result	Execution time	Memory
58848		hugo_pm	Chessboard (IZhO18_chessboard)	C++14	100 / 100	880 ms	44520 KiB

chessboard

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>
 
#define x1 X
#define x2 XX
#define y1 Y
#define y2 YY
 
#define mp make_pair
#define pb push_back
 
 
typedef long long ll;
typedef long double ld;
 
#define f first
#define s second
 
using namespace std;
 
const int N = 2e5 + 123;
 
int n, k, x1[N], x2[N], y1[N], y2[N];
 
ll ans = 1e18;
 
int get(int x, int side) {
  if (x < 0) return 0;
  int id = x / side;
  int ans = (id + 1) / 2 * side;
  if (!(id & 1)) ans += x % side + 1;
  return ans;
}
 
 
ll calc(int side) {
  if (side == n) return 1e18;
  ll even = 0, odd = 0;
  for (int i = 0;i < k;i++) {
    // number of even elements
    ll a1 = get(y2[i], side) - get(y1[i] - 1, side);
    ll a2 = y2[i] - y1[i] + 1 - a1;
    ll b1 = get(x2[i], side) - get(x1[i] - 1, side);
    ll b2 = x2[i] - x1[i] + 1 - b1;
    int idx = x1[i] / side;
    int idy = y1[i] / side;
    // row is odd
    if (idx & 1) {
      swap(a1, a2);
    } 
    // column is odd
    if (idy & 1) {
      swap(b1, b2);      
    }
   // cout << "i = " << i << " a1 = " << a1 << " a2 = " << a2 << " b1 = " << b1 << " b2 = " << b2 << endl;
   // cout << "x1 = " << x1[i] << " x2 = " << x2[i] << " y1 = " << y1[i] << " y2 = " << y2[i] << endl;
   // cout << "Ylen = " << y2[i] - y1[i] + 1 << endl;
    // 
    ll f0 = 1ll * a1 * b1 + 1ll * a2 * b2;
    ll f1 = 1ll * a2 * b1 + 1ll * a1 * b2;
    if (!((idx + idy) & 1)) swap(f0, f1);
    odd += f1;
    even += f0;
  }
  int cnt = n / side;
  ll tot = 1ll * cnt * cnt;
  // case 1 black - even, white - odd
  ll E = (tot / 2) * 1ll * side * side - even + odd;
  // case 2 black - odd, white - even
  ll O = (tot + 1) / 2 * 1ll * side * side - odd + even;
  return min(E, O);
}
 
int main() {
  #ifdef wws 
    freopen("input", "r", stdin);
  #endif
  scanf("%d%d", &n, &k);
  for (int i = 0;i < k;i++) {
    scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]);
    x1[i]--;
    x2[i]--;
    y1[i]--;
    y2[i]--;
  } 
  //cout << calc(1) << endl; return 0;
  for (int i = 1;1ll * i * i <= n;i++) {
    if (n % i == 0) {
      ans = min(ans, calc(i));
      if (n / i != i) ans = min(ans, calc(n / i));
    }
  }
  cout << ans << endl;
  return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &k);
   ~~~~~^~~~~~~~~~~~~~~~
chessboard.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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