Submission #879103

#	Time	Username	Problem	Language	Result	Execution time	Memory
879103		TheSahib	Chessboard (IZhO18_chessboard)	C++14	100 / 100	274 ms	8392 KiB

chessboard

#include <bits/stdc++.h>
 
#define ll long long
#define int ll
#define pii pair<int, int>
 
using namespace std;
 
const int MAX = 1e5 + 5;
const ll oo = 1e15;

ll n, k;

vector<array<int, 4>> v;

int f(int i, int d){
    if(i <= 0) return 0;
    int j = (i / d) * d;
    int a = ((j / d + 1) / 2) * d;
    if(!((j / d) & 1)) a += i - j;
    return a;
}
 
ll check(ll d){
    int pre[n + 1];
    pre[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        pre[i] = pre[i - 1] + (f(i, d) - f(i - 1, d));
    }
    
    ll a = f(n, d) * pre[n] + (n - f(n, d)) * (n - pre[n]);
    for(auto& x:v){
        int c1 = f(x[1], d) - f(x[0] - 1, d);
        int c2 = x[1] - x[0] + 1 - c1;
        int p = pre[x[3]] - pre[x[2] - 1];
        a -= 1ll * p * c1;
        a += 1ll * (x[3] - x[2] + 1 - p) * c1;
        a -= 1ll * (x[3] - x[2] + 1 - p) * c2;
        a += 1ll * p * c2;  
    }
    return min(a, n * n - a);
}
 
void solve(){
    scanf("%lld%lld", &n, &k);
    for (int i = 0; i < k; i++)
    {
        int x1, y1, x2, y2; scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
        v.push_back({x1, x2, y1, y2});
    }

    
    ll ans = oo;
    for (int i = 1; i * i <= n; i++)
    {
        if(n % i == 0){
            ans = min(ans, check(i));
            if(i != 1){
                ans = min(ans, check(n / i));
            }
        }
    }
    cout << ans << '\n';
}
/*
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
*/
 
signed main()
{
    solve();
}

Compilation message (stderr)

chessboard.cpp: In function 'void solve()':
chessboard.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf("%lld%lld", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
chessboard.cpp:49:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         int x1, y1, x2, y2; scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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