Submission #173244

#	Time	Username	Problem	Language	Result	Execution time	Memory
173244		LinusTorvaldsFan	Chessboard (IZhO18_chessboard)	C++14	100 / 100	1268 ms	4312 KiB

chessboard

#include <iostream>
#include <algorithm>
#include <vector>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
using namespace std;
 
typedef long long ll;
 
struct Rect{
  int x1,y1,x2,y2;
  Rect(int x1,int y1,int x2, int y2):x1(x1),y1(y1),x2(x2),y2(y2){}
  Rect(){}
};
 
const int maxk=100002;
Rect rects[maxk];
int n,k;
 
int up(int x, int y){
    return (x/y)+(x%y!=0);
}
 
vector<ll> get(int x1,int x2, int l){
  vector<ll> ans={0,0};  
  int nx1=up(x1,l)*l;
  
  if(nx1>x2){
    ans[(x1/l)&1]+=x2-x1+1;
    return ans;
  }
  
  ans[(x1/l)&1]+=nx1-x1;
  x1=nx1;
  
  int nx2=x2/l*l;
  
  ans[(x2/l)&1]+=x2-nx2;
  
  x2=nx2;
  
  if(x1>x2)return ans;
  ans[(x2/l)&1]++;
  x2--;
  if(x1>x2)return ans;
  int blocks=(x2-x1+1)/l;
  ans[(x1/l)&1]+=((blocks>>1)+(blocks&1))*l;
  ans[((x1/l)+1)&1]+=(blocks>>1)*l;
  return ans;
}
 
ll solve(ll l){
  ll black_colored_1=0;
  ll need_black_1=0;
  ll total_1=0;
  
  ll black_colored_2=0;
  ll need_black_2=0;
  ll total_2=0;
  auto t1=get(0,n-1,l);
  need_black_1+=t1[0]*t1[0]+t1[1]*t1[1];
  need_black_2+=t1[0]*t1[1]+t1[1]*t1[0];    
  
  for(int i=0;i<k;i++){
    auto t1=get(rects[i].x1-1,rects[i].x2-1,l);
    auto t2=get(rects[i].y1-1,rects[i].y2-1,l);
    black_colored_1+=t1[0]*t2[0]+t1[1]*t2[1];
    total_1+=t1[0]*t2[1]+t1[1]*t2[0];
    total_2+=t1[0]*t2[0]+t1[1]*t2[1];
    black_colored_2+=t1[0]*t2[1]+t1[1]*t2[0];
  }
  total_1+=need_black_1-black_colored_1;
  total_2+=need_black_2-black_colored_2;
  return min(total_1,total_2);
}
 
signed main(){
  //ios_base::sync_with_stdio(0); cin.tie(0);
  cin>>n;
  cin>>k;
  
  for(int i=0;i<k;i++){
    //cin>>rects[i].x1>>rects[i].y1>>rects[i].x2>>rects[i].y2;
    scanf("%d%d%d%d",&rects[i].x1,&rects[i].y1,&rects[i].x2,&rects[i].y2);
  }
  
  ll ans=1e18;
 
  for(int i=1;i*i<=n;i++){
    if(n%i==0){
      int l=i;
      if(l==n)continue;
      ans=min(ans,solve(l));
    }
    if(n%i==0){
      int l=n/i;
      if(l==n)continue;
      ans=min(ans,solve(l));
    }
  }
  cout<<ans;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d",&rects[i].x1,&rects[i].y1,&rects[i].x2,&rects[i].y2);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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