Submission #378648

#	Time	Username	Problem	Language	Result	Execution time	Memory
378648		eric_xiao	Chessboard (IZhO18_chessboard)	C++14	70 / 100	282 ms	512 KiB

chessboard

#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> can;
ll B[100009],C[100009];
ll cal(ll x,ll y,ll len)
{
    ll a = x/len,b = y/len;
    return (a+b+1)%2;
}
int main()
{
    ll N,M,i,j,k,x1,x2,y1,y2,a,b,c,d;
    cin >> N >> k;
    for(i = 1;i < N;i++)
    {
        if(N % i == 0) can.push_back(i);
    }
    for(i = 0;i < k;i++)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        x1--;
        y1--;
        x2--;
        y2--;
        for(j = 0;j < can.size();j++)
        {
            B[j] += cal(x1,y1,can[j]);
        }
    }
    ll ans = 10000000000000;
    for(i = 0;i < can.size();i++)
    {
        C[i] = k-B[i];
        ll tp = can[i];
        ll cnt = ((N/tp)*(N/tp)+1)/2;
        cnt *= tp*tp;
        ans = min({ans,cnt-B[i]+C[i],(N*N-cnt)-C[i]+B[i]});
    }
    cout << ans << endl;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:26:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(j = 0;j < can.size();j++)
      |                   ~~^~~~~~~~~~~~
chessboard.cpp:32:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(i = 0;i < can.size();i++)
      |               ~~^~~~~~~~~~~~
chessboard.cpp:13:10: warning: unused variable 'M' [-Wunused-variable]
   13 |     ll N,M,i,j,k,x1,x2,y1,y2,a,b,c,d;
      |          ^
chessboard.cpp:13:30: warning: unused variable 'a' [-Wunused-variable]
   13 |     ll N,M,i,j,k,x1,x2,y1,y2,a,b,c,d;
      |                              ^
chessboard.cpp:13:32: warning: unused variable 'b' [-Wunused-variable]
   13 |     ll N,M,i,j,k,x1,x2,y1,y2,a,b,c,d;
      |                                ^
chessboard.cpp:13:34: warning: unused variable 'c' [-Wunused-variable]
   13 |     ll N,M,i,j,k,x1,x2,y1,y2,a,b,c,d;
      |                                  ^
chessboard.cpp:13:36: warning: unused variable 'd' [-Wunused-variable]
   13 |     ll N,M,i,j,k,x1,x2,y1,y2,a,b,c,d;
      |                                    ^

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