Submission #340383

#	Time	Username	Problem	Language	Result	Execution time	Memory
340383		scales	Chessboard (IZhO18_chessboard)	C++17	70 / 100	497 ms	3564 KiB

chessboard

#include <bits/stdc++.h>
/*#ifndef LOCAL_RUN
    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC optimize("fast-math")
    #pragma GCC target("avx2,tune=native")
#endif*/
using namespace std;
int main()
{
      ios::sync_with_stdio(false);
      cin.tie(0);
     // freopen("input.txt","r",stdin);
     // freopen("output.txt","w",stdout);
     long long t,i,j,dno,x,y,z,w,m,k,n,x1,y1,tip,g,p,l,r,sum,maxi,kol,v,f,s,h,z1,rov;
     dno=0;
     cin>>n;
     cin>>k;
     z=0;
     tip=0;
     maxi=100000000000;
     vector<long long> a(k),b(k),c(k),d(k);
     for(i=0;i<k;i++)
     {
         cin>>a[i];
         cin>>b[i];
         cin>>c[i];
         cin>>d[i];
         a[i]--;
         b[i]--;
         c[i]--;
         d[i]--;
         tip=tip+(c[i]-a[i]+1)*(d[i]-b[i]+1);
     }
     vector<long long> viv;
     for(i=1;i<n;i++)
     {
         if(n%i==0)
         {
             viv.push_back(i);
         }
     }
     z1=viv.size();
     //cout<<"tip="<<tip<<endl;
     //cout<<"z1="<<z1<<endl;
        for(i=0;i<z1;i++)
        {
             kol=0;
             w=viv[i];
             //cout<<"w="<<w<<endl;
             //cout<<"w="<<w<<endl;
             for(j=0;j<k;j++)
             {
                 //cout<<"a="<<a[j]<<" b="<<b[j]<<" "<<a[j]%(2*w)<<" "<<b[j]%(2*w)<<endl;
                 z=(c[j]-a[j])/(2*w);
                 g=z*w;
                 x=a[j]%(2*w);
                 y=c[j]%(2*w);
                 if(x<=y)
                 {
                     l=x;
                     r=min(w-1,y);
                 }
                 else
                 {
                    swap(x,y);
                    l=x;
                    r=min(w-1,y);
                    rov=0;
                    rov=max(rov,r-l+1);
                    rov=w-rov;
                    r=rov;
                    l=1;
                 }
                 g=g+max(dno,(r-l+1));

                 z=(d[j]-b[j])/(2*w);
                 x=b[j]%(2*w);
                 y=d[j]%(2*w);
                 h=z*w;
                   // cout<<"h="<<h<<" z="<<z<<endl;
                 if(x<=y)
                 {
                     l=x;
                     r=min(w-1,y);
                 }
                 else
                 {
                    swap(x,y);
                    l=x;
                    r=min(w-1,y);
                    rov=0;
                    rov=max(rov,r-l+1);
                    rov=w-rov;
                    r=rov;
                    l=1;

                 }
                 //cout<<"h="<<h<<" dno="<<dno<<endl;
                 h=h+max(dno,(r-l+1));
                 //cout<<"g="<<g<<" h="<<h<<endl;
                 kol=kol+g*(d[j]-b[j]+1-h)+h*(c[j]-a[j]+1-g);

             }
             v=(n*n)/(w*w);
             if(v%2==0)
             {
                 f=n*n/2;
                 s=n*n/2;
             }
             else
             {
                 s=(n*n-w*w)/2;
                 f=n*n-s;
             }
             kol=tip-kol;
             //cout<<"kol="<<kol<<" f="<<f<<" s="<<s<<" maxi=";
             maxi=min({maxi,(f-kol+tip-kol),(kol+s-tip+kol)});
             //cout<<maxi<<endl;
        }
        cout<<maxi<<endl;
    return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:15:16: warning: unused variable 't' [-Wunused-variable]
   15 |      long long t,i,j,dno,x,y,z,w,m,k,n,x1,y1,tip,g,p,l,r,sum,maxi,kol,v,f,s,h,z1,rov;
      |                ^
chessboard.cpp:15:34: warning: unused variable 'm' [-Wunused-variable]
   15 |      long long t,i,j,dno,x,y,z,w,m,k,n,x1,y1,tip,g,p,l,r,sum,maxi,kol,v,f,s,h,z1,rov;
      |                                  ^
chessboard.cpp:15:40: warning: unused variable 'x1' [-Wunused-variable]
   15 |      long long t,i,j,dno,x,y,z,w,m,k,n,x1,y1,tip,g,p,l,r,sum,maxi,kol,v,f,s,h,z1,rov;
      |                                        ^~
chessboard.cpp:15:43: warning: unused variable 'y1' [-Wunused-variable]
   15 |      long long t,i,j,dno,x,y,z,w,m,k,n,x1,y1,tip,g,p,l,r,sum,maxi,kol,v,f,s,h,z1,rov;
      |                                           ^~
chessboard.cpp:15:52: warning: unused variable 'p' [-Wunused-variable]
   15 |      long long t,i,j,dno,x,y,z,w,m,k,n,x1,y1,tip,g,p,l,r,sum,maxi,kol,v,f,s,h,z1,rov;
      |                                                    ^
chessboard.cpp:15:58: warning: unused variable 'sum' [-Wunused-variable]
   15 |      long long t,i,j,dno,x,y,z,w,m,k,n,x1,y1,tip,g,p,l,r,sum,maxi,kol,v,f,s,h,z1,rov;
      |                                                          ^~~

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