oj.uz

Submission #89445

# Submission time Handle Problem Language Result Execution time Memory
89445 2018-12-14T16:36:29 Z Harvey_Rollens Chessboard (IZhO18_chessboard) C++17
8 / 100
 31 ms 2492 KB 
#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) 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];

    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))
            {
                kb+=(l*r)/2+(l*r)%2;
                kch+=(l*r)/2;
            }
            else
            {
                kb+=(l*r)/2;
                kch+=(l*r)/2+(l*r)%2;
            }

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

        cout<<min(kb, kch);
        return 0;
    }

    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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 572 KB Output is correct
6 Correct 2 ms 572 KB Output is correct
7 Correct 2 ms 572 KB Output is correct
8 Correct 2 ms 688 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 2492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2492 KB Output is correct
2 Correct 2 ms 2492 KB Output is correct
3 Correct 2 ms 2492 KB Output is correct
4 Correct 3 ms 2492 KB Output is correct
5 Correct 3 ms 2492 KB Output is correct
6 Correct 2 ms 2492 KB Output is correct
7 Correct 3 ms 2492 KB Output is correct
8 Correct 2 ms 2492 KB Output is correct
9 Correct 2 ms 2492 KB Output is correct
10 Incorrect 2 ms 2492 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2492 KB Output is correct
2 Correct 2 ms 2492 KB Output is correct
3 Correct 2 ms 2492 KB Output is correct
4 Correct 3 ms 2492 KB Output is correct
5 Correct 3 ms 2492 KB Output is correct
6 Correct 2 ms 2492 KB Output is correct
7 Correct 3 ms 2492 KB Output is correct
8 Correct 2 ms 2492 KB Output is correct
9 Correct 2 ms 2492 KB Output is correct
10 Incorrect 2 ms 2492 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 2492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 572 KB Output is correct
6 Correct 2 ms 572 KB Output is correct
7 Correct 2 ms 572 KB Output is correct
8 Correct 2 ms 688 KB Output is correct
9 Incorrect 31 ms 2492 KB Output isn't correct
10 Halted 0 ms 0 KB -