Submission #48825

#	Time	Username	Problem	Language	Result	Execution time	Memory
48825		mrtsima22	Chessboard (IZhO18_chessboard)	C++17	8 / 100	31 ms	2536 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;
#define lo long
const int lmax=1999999999;
const long long lmx=1999999999999999999;
long long n;
long long k;
long long ans=lmax,ansT,ansS;
long long a[100003],b[100003],c[100003],d[100004];
vector<long long>v;
long long k1;
int main(){std::ios::sync_with_stdio(false);
cin>>n>>k;
if(k==0LL){
ans=n*n/2;
for(long long j=2;j<=n/2+1;j++)
{
	if(n%j==0)
	{
		long long k=n/j;
		k=k*k;
		ans=min(ans,j*j/2*k);
	}
}
cout<<ans<<endl;
return 0;
}
ansT=ansS=0LL;
for(long long i=2LL;i<n;i++)
{
	if(n%i==0)
	{
		v.push_back(i);
	}
}
for(int i=0;i<k;i++)
	cin>>a[i]>>b[i]>>c[i]>>d[i];
for(int j=0;j<v.size();j++){
long long p=v[j];
for(int i=0;i<k;i++)
{
	if(a[i]==c[i]&&b[i]==d[i])
	{
		long long q1=(a[i]-1)/p+1;
		long long q2=(b[i]-1)/p+1;
		long long q=q1+q2;
		if((q)&1)
		{
			ansT++;
		}
		else
		{
			ansS++;
		}
	}	
}
long long O=n/v[j];
//---------------
k1=n*n/2;
long long K=k1;
if(n&1)K++;
ans=min(ansT+K-ansS,ansS+k1-ansT);
//--------------
k1=v[j]*v[j]/2*O*O;
K=n*n-k1;
ans=min(ansS+k1-ansT,ansT+K-ansS);
}
//cout<<ansT+K-ansS<<" "<<ansS+k-ansT<<endl;
cout<<ans<<endl;
}
/*

                   *         *
                  * *       * *
                 *   *     *   *
                *     *   *     *
               *       * *       *
               *        *        *
                *               *
                 *             *
                  *           *
                   *         *
                    *       *
                     *     *
                      *   *
                       * *
                        *



*/

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:38:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int j=0;j<v.size();j++){
             ~^~~~~~~~~

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