Submission #81005

#	Time	Username	Problem	Language	Result	Execution time	Memory
81005		ToadDaveski	Chessboard (IZhO18_chessboard)	C++14	70 / 100	498 ms	2304 KiB

chessboard

#include <bits/stdc++.h>
#define ll long long
#define fr first
#define sc second
using namespace std;
pair <ll,ll> a[100001];
int main()
{
    ll n,m,i,j;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        ll x,y;
        cin>>x>>x>>x>>y;
        a[i]={x,y};
    }
    ll ans=1e10;
    for(i=1;i<=sqrt(n);i++)
    {
        if (n%i==0)
        {
            ll raz=i;ll  izm=0;
            ll kolb=(((n*n)/(i*i)))/2*i*i;
            ll kolw=((((n*n)/(i*i)))/2+(((n*n)/(i*i))%2))*i*i;
            for(ll j=1;j<=m;j++)
            {
                ll x=(a[j].fr/i)+(a[j].fr%i>0),y=(a[j].sc/i)+(a[j].sc%i>0);
                if ((x+y)%2==1)
                    izm++;
            }
            ans=min(ans,min(izm+(kolw-(m-izm)),(m-izm)+(kolb-izm)));
            //cout<<ans<<" "<<i<<" "<<izm<<" "<<kolb<<" "<<kolw<<endl;
            if (i==1) continue;
            raz=i;
            i=n/i;
            izm=0;
            kolb=(((n*n)/(i*i)))/2*i*i;
            kolw=((((n*n)/(i*i)))/2+(((n*n)/(i*i))%2))*i*i;
            for(ll j=1;j<=m;j++)
            {
                ll x=a[j].fr/i+(a[j].fr%i>0),y=(a[j].sc/i)+(a[j].sc%i>0);
                if ((x+y)%2==1)
                    izm++;
            }
            ans=min(ans,min(izm+(kolw-(m-izm)),(m-izm)+(kolb-izm)));
            //cout<<ans<<" "<<i<<" "<<izm<<endl;
            i=raz;
        }
    }
    cout<<ans;
    return 0;
}
/*
6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6
*/

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:9:14: warning: unused variable 'j' [-Wunused-variable]
     ll n,m,i,j;
              ^

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