oj.uz

Submission #173975

# Submission time Handle Problem Language Result Execution time Memory
173975 2020-01-06T04:04:04 Z juggernaut Chessboard (IZhO18_chessboard) C++14
8 / 100
 50 ms 3704 KB 
//Just try and the idea will come
#include<bits/stdc++.h>
#define int long long int
#define fr first
#define sc second
using namespace std;
int n,k,i,j,x,y,res;
pair<int,int>p1[100001],p2[100001];
inline int get_x(int kk,int x,int white){
    int res;
    if(white)res=((x/kk+1)>>1)*kk;
    else res=((x/kk)>>1)*kk;
    if(((x+kk-1)/kk)&1==white)res+=(x%kk);
    return res;
}
inline int get_xy(int kk,int y,int x){
    if(x==0||y==0)return 0;
    int res=(((x/kk)*(y/kk)+1)>>1)*kk*kk,a,b;
    a=(x+kk-1)/kk;b=(y+kk-1)/k;
    res+=(x%kk)*get_x(kk,y,a&1);
    res+=(y%kk)*get_x(kk,x,b&1);
    if(!((a+b)&1))res-=(x%k)*(y%k);
    return res;
}
inline int get_range(int kk,int x,int y,int x2,int y2){
    return get_xy(kk,x2,y2)+get_xy(kk,x-1,y-1)-get_xy(kk,x-1,y2)-get_xy(kk,x2,y-1);
}
inline int get(int f){
    int cnt=0,c[2],wh,bl;
    c[0]=f*f*(((n/f)*(n/f))>>1);
    c[1]=f*f*(((n/f)*(n/f)+1)>>1);
    for(int i=0;i<k;i++){
        //c[(p[i].fr/f+p[i].sc/f)%2]++;
        wh=get_range(f,p1[i].first,p1[i].second,p2[i].first,p2[i].second);
        bl=(abs(p1[i].second-p2[i].second)+1)*(abs(p1[i].first-p2[i].first)+1)-wh;
        c[0]-=bl;
        c[0]+=wh;
        swap(bl,wh);
        c[1]-=bl;
        c[1]+=wh;
    }
    return min(c[0],c[1]);
}
main(){
    scanf("%lld%lld",&n,&k);
    for(i=0;i<k;i++){
        scanf("%lld%lld%lld%lld",&p1[i].fr,&p1[i].sc,&p2[i].fr,&p2[i].sc);
    }
    res=get(1);
    for(j=2;j*j<=n;j++){
        if(n%j==0){
            res=min(res,get(j));
            res=min(res,get(n/j));
        }
    }
    printf("%lld",res);
}
/*
int get_x(int k,int x,int white){
    int res;
    if(white)res=((x/k+1)/2)*k;
    else res=((x/k)/2)*k;
    if(((x+k-1)/k)%2==white)res+=(x%k);
    return res;
}
int get_xy(int k,int y,int x){
    int res=(((x/k)*(y/k)+1)/2)*k*k,a,b;
    a=(x+k-1)/k;b=(y+k-1)/k;
    res+=(x%k)*get_x(k,y,a%2);
    res+=(y%k)*get_x(k,x,b%2);
    if(!((a+b)&1))res-=(x%k)*(y%k);
    return res;
}
*/

Compilation message

chessboard.cpp: In function 'long long int get_x(long long int, long long int, long long int)':
chessboard.cpp:13:23: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
     if(((x+kk-1)/kk)&1==white)res+=(x%kk);
                      ~^~~~~~~
chessboard.cpp: In function 'long long int get(long long int)':
chessboard.cpp:29:9: warning: unused variable 'cnt' [-Wunused-variable]
     int cnt=0,c[2],wh,bl;
         ^~~
chessboard.cpp: At global scope:
chessboard.cpp:44:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
chessboard.cpp: In function 'int main()':
chessboard.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&n,&k);
     ~~~~~^~~~~~~~~~~~~~~~~~
chessboard.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld%lld",&p1[i].fr,&p1[i].sc,&p2[i].fr,&p2[i].sc);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 6 ms 376 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 3704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 3704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 6 ms 376 KB Output is correct
9 Incorrect 50 ms 3704 KB Output isn't correct
10 Halted 0 ms 0 KB -