Submission #89446

#	Time	Username	Problem	Language	Result	Execution time	Memory
89446		Harvey_Rollens	Chessboard (IZhO18_chessboard)	C++17	8 / 100	28 ms	2476 KiB

chessboard

#include<bits/stdc++.h>
#define ll long long
#define st string
#define fr first
#define se second

const long long mod=1e9+7;

using namespace std;

vector<pair<ll, ll> > v;
ll a[100100], b[100100], k, ans=1000000100, a1[100100], b1[100100];

void f(ll x)
{
    for(ll i=1; i*i<=x; i++)
    {
        if(x%i==0)
        {
            v.push_back({i, x/i});
            if(i>1 && i!=x/i) v.push_back({x/i, i});
        }
    }
}

void pro(ll p, ll o)
{
    ll kb1=0, kb2=0;
    for(ll i=1; i<=k; i++)
    {
        ll x=a[i], y=b[i];

        x=(x+p-1)/p;
        y=(y+p-1)/p;

        if((x%2!=0 && y%2!=0) || (x%2==0 && y%2==0))
        {
            kb1++;
        }
        else kb2++;
    }

    //cout<<"kb1="<<kb1<<" kb2="<<kb2<<endl;

    kb2=kb2+((o*o)/2+(o*o)%2)*p*p-(k-kb2);
    kb1=kb1+((o*o)/2)*p*p-(k-kb1);

    //cout<<"PPP= "<<kb1<<" "<<kb2<<" "<<p<<" "<<o<<'\n';

    ans=min(kb1, min(ans, kb2));
}

main()
{
    //freopen("1.txt", "r", stdin);
    //freopen("1.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    ll n;
    cin>>n>>k;

    f(n);

    for(ll i=1; i<=k; i++)
        cin>>a[i]>>b[i]>>a1[i]>>b1[i];

    //cout<<v.size()<<endl;

    if(v.size()==1)
    {
        ll kch=0, kb=0, s=0;
        for(ll i=1; i<=k; i++)
        {
            ll x=a[i], y=b[i], x1=a1[i], y1=b1[i];
            ll l=(x1-x)+1, r=(y1-y)+1;

            if((x%2==0 && x%2==0) || (x%2!=0 && y%2!=0))
            {
                kch+=(l*r)/2+(l*r)%2;
                kb+=(l*r)/2;
            }
            else
            {
                kch+=(l*r)/2;
                kb+=(l*r)/2+(l*r)%2;
            }

            s+=(l*r);
        }
        //cout<<kb<<" "<<kch<<endl;

        kch=kch+(n*n)/2-(s-kch);
        kb=kb+(n*n)/2+(n*n)%2-(s-kb);

        cout<<min(kb, kch);
        return 0;
    }
    //cout<<"ANS"<<endl;

    for(ll i=0; i<v.size(); i++)
    {
        //cout<<v[i].fr<<" "<<v[i].se<<endl;
        pro(v[i].fr, v[i].se);
    }

    cout<<ans;
    return 0;
}
/*
3 5
1 1 1 1
1 3 1 3
2 2 2 2
3 1 3 1
3 3 3 3
*/

Compilation message (stderr)

chessboard.cpp:53:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
chessboard.cpp: In function 'int main()':
chessboard.cpp:102:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=0; i<v.size(); i++)
                 ~^~~~~~~~~

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