Submission #721116

#	Time	Username	Problem	Language	Result	Execution time	Memory
721116		cig32	Chessboard (IZhO18_chessboard)	C++17	100 / 100	523 ms	5844 KiB

chessboard

#include "bits/stdc++.h"
#define int long long
using namespace std;
const int MAXN = 1e5 + 10;
void solve(int tc) {
  int n,k;
  cin >> n>>k;
  int x1[k],y1[k],x2[k],y2[k];
  for(int i=0; i<k; i++) {
    cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
    x1[i]--; y1[i]--;
    x2[i]--; y2[i]--;
  }
  vector<int> prof;
  for(int i=1; i*i<=n; i++) {
    if(n%i == 0) {
      prof.push_back(i);
      if(i*i!=n && i!=1) prof.push_back(n/i);
    }
  }
  sort(prof.begin(), prof.end());
  int ans = 1e18;
  for(int s: prof) {
    int c[2] = {0, 0}; // number of black cells for each (i/S + j/S) mod 2
    for(int i=0; i<k; i++) {
      int type0 = 0;
      int type1 = 0;
      int l = y1[i], r = y2[i];
      if(l / (2*s) == r / (2*s)) {
        if(r % (2*s) < s) type0 += r-l+1;
        else if(l % (2*s) >= s) type0 += 0;
        else type0 += s - (l % (2*s));
      }
      else {
        if(l % (2*s) >= s) {
          int md = l % (2*s);
          l += 2*s - md;
        }
        else {
          int md = l % (2*s);
          type0 += s - md;
          l += 2*s - md;
        }
        if(r % (2*s) >= s) {
          int md = r % (2*s);
          r -= md+1;
          type0 += s;
        }
        else {
          int md = r % (2*s);
          r -= md+1;
          type0 += md+1;
        }
        type0 += (r-l+1) / 2;
      }
      type1 = y2[i]-y1[i]+1 - type0;
      l = x1[i], r = x2[i];
      int type2 = 0;
      int type3 = 0;
      if(l / (2*s) == r / (2*s)) {
        if(r % (2*s) < s) type2 += r-l+1;
        else if(l % (2*s) >= s) type2 += 0;
        else type2 += s - (l % (2*s));
      }
      else {
        if(l % (2*s) >= s) {
          int md = l % (2*s);
          l += 2*s - md;
        }
        else {
          int md = l % (2*s);
          type2 += s - md;
          l += 2*s - md;
        }
        if(r % (2*s) >= s) {
          int md = r % (2*s);
          r -= md+1;
          type2 += s;
        }
        else {
          int md = r % (2*s);
          r -= md+1;
          type2 += md+1;
        }
        type2 += (r-l+1) / 2;
      }
      type3 = x2[i]-x1[i]+1 - type2;
      //cout<<s<<" "<<type0<<" "<<type1<<" "<<type2<<" "<<type3<<"\n";
      int d = type0 * type2 + type1 * type3;
      c[0] += d;
      c[1] += (x2[i] - x1[i] + 1) * (y2[i] - y1[i] + 1) - d;
    }
    int t[2] = {0, 0};
    int nums = (n/s) * (n/s);
    t[0] = s*s * ((nums+1) / 2);
    t[1] = s*s * (nums / 2);
    ans = min(ans, abs(t[0] - c[0]) + c[1]);
    ans = min(ans, abs(t[1] - c[1]) + c[0]);
   // cout<<ans<<"\n";
  }
  cout << ans << "\n";
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t=1; //cin>>t;
  for(int i=1; i<=t; i++)solve(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