Submission #872664

#	Time	Username	Problem	Language	Result	Execution time	Memory
872664		epicci23	Chessboard (IZhO18_chessboard)	C++17	39 / 100	2068 ms	18108 KiB

chessboard

#include "bits/stdc++.h"
using namespace std;
#define int long long
#pragma GCC optimize ("O3") 
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define endl '\n'

/*
 implement and debug smart
 DONT GET STUCK ON ONE APPROACH
 write smth on paper
 edge cases (n=1?)
 rewrite the problem
 simplify
 transform the problem into other problem
*/


void solve(){

  int n,k;
  cin >> n >> k;
 
  vector<array<int,4>> v;

  int ans = n * n;

  for(int i=1;i<=k;i++){
     int a,b,c,d;
     cin >> a >> b >> c >> d;
     a--;
     b--;
     c--;
     d--;
     v.pb({a,b,c,d});
  }  
  
   auto f = [](array<int,4> a,array<int,4> b)->array<int,4>{
     int xl,xr,yl,yr;
     xl=max(a[0],b[0]);
     xr=min(a[2],b[2]);
     yl=max(a[1],b[1]);
     yr=min(a[3],b[3]);
     if(xl<=xr && yl<=yr) return {xl,yl,xr,yr};
     else return {-1,-1,-1,-1};
  };

  for(int i=1;i<n;i++){

  	if(n%i) continue;
    
    // 1 siyah
    // 0 beyaz

    int cur = 0;
    map<array<int,2>,vector<array<int,4>>> mp;

    int kac_siyah = (n / i) * ( (n / i) / 2);
    if((n/i)&1) kac_siyah +=  (n / i) / 2;

    for(auto x : v){
      int aa = x[0]-(x[0]%i);
      int bb = x[1]-(x[1]%i);

      for(int a=aa;a<=n;a+=i){
	       for(int b=bb;b<=n;b+=i){
		      if(f(x,{a,b,a+i-1,b+i-1})[0]!=-1)
		       mp[{a,b}].pb(f(x,{a,b,a+i-1,b+i-1}));
		      else break;
	       }
      }
    }

    for(auto x:mp){
      int col = (x.first[0] / i + x.first[1] / i) & 1;
      int hm = 0;
      for(auto y:x.second) hm+=(y[2]-y[0]+1)*(y[3]-y[1]+1);
      if(col) cur+=i*i-hm;
      else cur+=hm;
      if(col) kac_siyah--;
    }
    
    //cout << i << ": " << kac_siyah << endl;
    cur += kac_siyah * i * i;
    ans=min(ans,cur);
    
    cur=0;
    kac_siyah = (n / i) * ( (n/i) / 2);
    if((n/i)&1) kac_siyah +=  (n / i + 1) / 2;

    for(auto x:mp){
      int col = (x.first[0] / i + x.first[1] / i) & 1;
      col^=1;
      int hm = 0;
      for(auto y:x.second) hm+=(y[2]-y[0]+1)*(y[3]-y[1]+1);
      if(col) cur+=i*i-hm;
      else cur+=hm;
      if(col) kac_siyah--;
    }

    cur += kac_siyah * i * i;
    //cout << i << ": " << kac_siyah << endl;
    ans=min(ans,cur);
  }

  cout << ans << endl;
}

int32_t main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();
}

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