Submission #89443

#	Time	Username	Problem	Language	Result	Execution time	Memory
89443		Harvey_Rollens	Chessboard (IZhO18_chessboard)	C++17	31 / 100	143 ms	3632 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;

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) 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;

    if(!k)
    {
        cout<<(n*n)/2;
        return 0;
    }
    f(n);

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

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

    cout<<ans;
    return 0;
}
/*
*/

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:74:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=0; i<v.size(); i++)
                 ~^~~~~~~~~

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