Submission #338442

#	Time	Username	Problem	Language	Result	Execution time	Memory
338442		boykut	Chessboard (IZhO18_chessboard)	C++14	70 / 100	268 ms	3436 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

#define int long long

int isprime(int n) {
   if (n == 2) return false;
   for (int i = 2; i < n; i++) {
      if (n % i == 0) return false;
   }
   return true;
}

signed main() {
   ios::sync_with_stdio(0);
   cin.tie(0);
   int n, k;
   cin >> n >> k;
   vector <int> x1(k), x2(k), y1(k), y2(k);
   for (int i = 0; i < k; i++) {
      cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
   }
   
   // subtest1
   if (k == 0) {
      int ans = -1;
      for (int i = 1; i < n; i++) {
         if (n % i == 0) {
            int res = ((n * n) / (i * i)) / 2 * (i * i);
            if (ans == -1 || ans > res)
               ans = res;
         }
      }
      cout << ans << '\n';
      return 0;
   }
   
   /// subtest2
   bool ok = true;
   for (int i = 0; i < k; i++) {
      if (x1[i] != x2[i] || y1[i] != y2[i])
         ok = false;
   }
   if (ok && isprime(n)) {      
      int cnt[] = {0, 0};
      for (int i = 0, x, y; i < k; i++) {
         x = x1[i]; y = y1[i];
         cnt[(x + y) % 2]++;
      }
      if (n == 2) {
         cout << min(2 - cnt[0] + cnt[1], 2 - cnt[1] + cnt[0]);
      } else {
         cout << min(n * n / 2 + 1 - cnt[0] + cnt[1], n * n / 2 - cnt[1] + cnt[0]);
      }
      return 0;
   }
   
   // stupid //subtest3, subtes4
   if (n <= 0) {
      cerr << "3, 4" << '\n';
      vector <vector <int> > sum(1+n,vector <int> (1+n, 0));
      for (int i = 0; i < k; i++) {
         for (int x = x1[i]; x <= x2[i]; x++)
            for (int y = y1[i]; y <= y2[i]; y++)
               sum[x][y] = 1;
      }
      //for (int i = 1; i <= n; i++) {
      //   for (int j = 1; j <= n; j++) {
      //      cout << sum[i][j] << ' ';
      //   }
      //   cout << '\n';
      //}
      //cout << '\n';
      for (int i = 1; i <= n; i++) {
         for (int j = 1; j <= n; j++) {
            sum[i][j] += sum[i][j-1];
            sum[i][j] += sum[i-1][j];
            sum[i][j] -= sum[i-1][j-1];
         }
      }
      //for (int i = 1; i <= n; i++) {
      //   for (int j = 1; j <= n; j++) {
      //      cout << sum[i][j] << ' ';
      //   }
      //   cout << '\n';
      //}
      //cout << '\n';
      vector <int> div;
      for (int i = 1; i < n; i++)
         if (n % i == 0)
            div.push_back(i);
      int ans = 9e18;
      for (auto D: div) {
         int cnt[] = {0, 0};
         int pos = 1;
         for (int i = 1;; i += D) {
            if (i + D - 1 > n) break;
            int par = (pos & 1);
            for (int j = 1;; j += D) {
               if (j + D - 1 > n) break;
               int i2 = i + D - 1, j2 = j + D - 1;
               int A = sum[i2][j2];
               A -= sum[i2][j-1];
               A -= sum[i-1][j2];
               A += sum[i-1][j-1];
               cnt[par] += A;
               par ^= 1;
            }
            pos++;
         }
         //cout << D << ' ' << cnt[1] << ' ' << cnt[0] << '\n';
         int sc = ((n*n)/(D*D))/2*(D*D);
         int fr = ((n*n)/(D*D)+1)/2*(D*D);
         //cout << min({fr-cnt[1]+cnt[0],sc-cnt[0]+cnt[1]}) << '\n';
         ans = min({ans, fr-cnt[1]+cnt[0], sc-cnt[0]+cnt[1]});
      }
      cout << ans << '\n';
   } else if (n <= 100000) {
      cerr << "5" << '\n';
      vector <int> div;
      for (int i = 1; i < n; i++)
         if (n % i == 0)
            div.push_back(i);
      int ans = n * n;
      for (auto D: div) {
         int cnt[] = {0, 0};
         for (int i = 0; i < k; i++) {
            int x = (x1[i] + D - 1) / D, y = (y1[i] + D - 1) / D;
            if (x % 2 == y % 2) {
               cnt[1] ++;
            } else {
               cnt[0] ++;
            }
         }
         //cout << D << ' ' << cnt[1] << ' ' << cnt[0] << '\n';
         int sc = ((n*n)/(D*D))/2*(D*D);
         int fr = ((n*n)/(D*D)+1)/2*(D*D);
         //cout << min({fr-cnt[1]+cnt[0],sc-cnt[0]+cnt[1]}) << '\n';
         ans = min({ans, fr-cnt[1]+cnt[0], sc-cnt[0]+cnt[1]});
      }
      cout << ans << '\n';
   }
   return 0;
}

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