Submission #133419

#	Time	Username	Problem	Language	Result	Execution time	Memory
133419		Kastanda	Chessboard (IZhO18_chessboard)	C++11	100 / 100	228 ms	5084 KiB

chessboard

// ItnoE
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 100005;
int n, k, dp[N], dp2[N];
pair < int , int > A[N], B[N];
inline long long Solve(int d)
{
    long long tot = n / d;
    tot *= tot; tot = (tot + 1) >> 1;
    tot *= 1LL * d * d;
    for (int i = 1; i <= n; i ++)
        dp[i] = dp[i - 1] + ((i - 1) / d % 2 == 0), dp2[i] = i - dp[i];
    for (int i = 0; i < k; i ++)
    {
        int ax = dp[B[i].first] - dp[A[i].first];
        int bx = dp2[B[i].first] - dp2[A[i].first];
        int ay = dp[B[i].second] - dp[A[i].second];
        int by = dp2[B[i].second] - dp2[A[i].second];
        tot -= 1LL * ax * ay;
        tot -= 1LL * bx * by;
        tot += 1LL * ax * by;
        tot += 1LL * bx * ay;
    }
    return (min(tot, 1LL * n * n - tot));
}
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < k; i ++)
        scanf("%d%d%d%d", &A[i].x, &A[i].y, &B[i].x, &B[i].y), A[i].x --, A[i].y --;
    long long Mn = LLONG_MAX;
    for (int d = 1; d < n; d ++)
        if (n % d == 0)
            Mn = min(Mn, Solve(d));
    return !printf("%lld\n", Mn);
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~
chessboard.cpp:33:73: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &A[i].x, &A[i].y, &B[i].x, &B[i].y), A[i].x --, A[i].y --;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

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