Submission #169433

#	Time	Username	Problem	Language	Result	Execution time	Memory
169433		RafaelSus	Chessboard (IZhO18_chessboard)	C++14	70 / 100	279 ms	7032 KiB

chessboard

#include <bits/stdc++.h>
 
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
const ll inf=1e18+18ll;
#define pb push_back
 
ll n,k;
ll a[N];

vector<int> J[N];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  
  
  int n;
  cin>>n>>k;
  /*if(k==0){
    cout<<(n*1ll*n/2ll)<<'\n';
    return 0;
  }*/
  for(int i=0;i<k;i++){
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    J[y1].push_back(n-x1+1);
  }
  vector<int> div;div.push_back(1);
  for(int i=2;i*i<=n;i++){
    if(n%i==0){
      div.push_back(i);
      if(n/i!=i)div.push_back(n/i);
    }
  }
  sort(div.begin(),div.end());
  ll answ=n*1ll*n;
  for(int i=0;i<div.size();i++){
    ll tmp=0ll;
    //cerr<<div[i]<<' ';
    ll x=n/div[i];
    if(x%2){ll y=x/2+1,z=x/2;tmp=y*y+z*z;}
    else{ll y=x/2;tmp=y*y+y*y;}
    tmp=tmp*1ll*div[i]*1ll*div[i];//cerr<<tmp<<' ';
    for(int j=1;j<=n;j++){//cerr<<tmp<<' ';
      for(int p=0;p<J[j].size();p++){
        if(j%div[i]==0){
          if((j/div[i])%2){
            if(J[j][p]%div[i]==0){
              if((J[j][p]/div[i])%2){
                tmp--;
              }else tmp++;
            }else if((J[j][p]/div[i])%2==0){
              tmp--;
            }else tmp++;
          }else{
            if(J[j][p]%div[i]==0){
              if((J[j][p]/div[i])%2==0){
                tmp--;
              }else tmp++;
            }else if((J[j][p]/div[i])%2==1){
              tmp--;
            }else tmp++;
          }
        }else if((j/div[i])%2==0){
          if(J[j][p]%div[i]==0){
            if((J[j][p]/div[i])%2){
              tmp--;
            }else tmp++;
          }else if((J[j][p]/div[i])%2==0){
            tmp--;
          }else tmp++;
        }else if((j/div[i])%2==1){
          if(J[j][p]%div[i]==0){
            if((J[j][p]/div[i])%2==0){
              tmp--;
            }else tmp++;
          }else if((J[j][p]/div[i])%2==1){
            tmp--;
          }else tmp++;
        }
      }//cerr<<tmp<<' ';
    }
    answ=min(answ,min(tmp,n*1ll*n-tmp));
    //cerr<<answ<<'\n';
  }
  cout<<answ<<'\n';
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:39:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<div.size();i++){
               ~^~~~~~~~~~~
chessboard.cpp:47:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int p=0;p<J[j].size();p++){
                   ~^~~~~~~~~~~~

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