Submission #1128834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128834		Johan	Chessboard (IZhO18_chessboard)	C++20	39 / 100	211 ms	327680 KiB

chessboard

#include <bits/stdc++.h>
using namespace std; 
# define ld long double
# define lld long long double
# define endl "\n"

const int mod = 1e9 + 7;
const int maxn = 1e5 + 6;
const int INF = 1e18;

template < typename T > void print(vector < T > x){  for(auto i : x)    cout << i << ' ';  cout << endl;}
template < typename T > T ceil(T a, T b){ if(a % b == 0){return a / b;} else{return a / b + 1;}}
template < typename T > T floor(T a, T b){ if(a % b == 0){return a / b;} else{return a / b + 0;}}
template < typename T > T lcm(T a, T b){ return (a * b) / gcd(a, b);}

int combine(int a, int b, int n){
  if(n == 1){return a + b;}
  if(n == 2){return a - b;}
  if(n == 3){return gcd(a, b);}
  if(n == 4){return lcm(a, b);}   
  if(n == 5){return max(a, b);}
  if(n == 6){return min(a, b);}
}

template < typename T >
T dis(T x1, T y1, T x2, T y2){
  return (sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
}

template < typename T >
T SUM(vector < T > x){
  int ans = 0;
  for(auto i : x)  ans = abs(ans + i);
  return ans; 
}

template < typename T > 
T power(T a, T n, T m){
  if(n == 0)  return 1;
  if(n % 2 == 0)  return power(((a % m) * (a % m)) % m , n / 2, m);
  return ((a % m) * power(a, n - 1, m)) % m;
}

void solve()  
{ 
  int n, k, mn = INF;
  cin >> n >> k;
  vector < vector < bool > > cur(n + 1, vector < bool > (n + 1, 0));
  for(int i = 1; i <= k; i++){
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    cur[x1][y1] = 1;
  }
  for(int chk = 1; chk <= n / 2; chk++){
    vector < vector < bool > > prob(n + 1, vector < bool > (n + 1, 0));
    vector < vector < bool > > probc(n + 1, vector < bool > (n + 1, 0));
    if(n % chk) continue;
    int b = 1;
    int ans1 = 0, ans2 = 0;
    for(int i = 1; i <= n; i++){
      if(b){
        int bc = 1;
        for(int j = 1; j <= n; j++){
          prob[i][j] = bc;
          probc[i][j] = bc ^ 1;
          if(!(j % chk)) bc = bc ^ 1;
        }
        if(!(i % chk))  b = b ^ 1;
      }
      else {
        int bc = 0;
        for(int j = 1; j <= n; j++){
          prob[i][j] = bc;
          probc[i][j] = bc ^ 1;
          if(!(j % chk)) bc = bc ^ 1;
        }
        if(!(i % chk))  b = b ^ 1;
      }
    }
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= n; j++){
        if(prob[i][j] != cur[i][j])
          ans1++;
        if(probc[i][j] != cur[i][j])
          ans2++;
      }
    }
    mn = min({mn, ans1, ans2});
  }
  cout << mn << endl;
}

signed main()
{   
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tt = 1;
  // cin >> tt;
  while(tt--){
    solve();
  }
}   

Compilation message (stderr)

chessboard.cpp:9:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    9 | const int INF = 1e18;
      |                 ^~~~
chessboard.cpp: In function 'int combine(int, int, int)':
chessboard.cpp:23:1: warning: control reaches end of non-void function [-Wreturn-type]
   23 | }
      | ^

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