Submission #747062

#	Time	Username	Problem	Language	Result	Execution time	Memory
747062		heeheeheehaaw	Chessboard (IZhO18_chessboard)	C++17	70 / 100	309 ms	5816 KiB

chessboard

#include <iostream>
#include <vector>
#define int long long

using namespace std;

int a[1005][1005];
int spw[1005][1005], spb[1005][1005];
int x1[100005], x2[100005], y1[100005], y2[100005];

signed main()
{
    int s1 = 0, s2 = 0;
    int n, k;
    cin>>n>>k;

    vector<int> divs;
    for(int i = 1; i * i <= n; i++)
        if(n % i == 0)
        {
            divs.push_back(i);
            if(i * i != n && i != 1)
                divs.push_back(n / i);
        }

    for(int i = 1; i <= k; i++)
        cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];

    int minn = n * n;
    for(auto d : divs)
    {
        int s1 = 0, s2 = 0;
        for(int i = 1; i <= k; i++)
        {
            int c1 = (x1[i] - 1) / d + 1;
            int c2 = (y1[i] - 1) / d + 1;
            if((c1 + c2) % 2 == 0)
                s1++;
            else
                s2++;
        }

        int d1 = n * n, d2 = n * n;
        int nli = n / d / 2, nlp = n / d / 2;
        if((n / d) % 2 == 1) nli++;

        d2 -= (d * d * (nli * nli + nlp * nlp));
        d1 = n * n - d2;
        int ans = min(d1 - s1 + s2, d2 - s2 + s1);
        minn = min(minn, ans);
    }

    cout<<minn<<'\n';

    return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:13:9: warning: unused variable 's1' [-Wunused-variable]
   13 |     int s1 = 0, s2 = 0;
      |         ^~
chessboard.cpp:13:17: warning: unused variable 's2' [-Wunused-variable]
   13 |     int s1 = 0, s2 = 0;
      |                 ^~

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