Submission #895266

#	Time	Username	Problem	Language	Result	Execution time	Memory
895266		Andrey	Chessboard (IZhO18_chessboard)	C++14	70 / 100	282 ms	4388 KiB

chessboard

#include<bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n,k,x,y,ans = LLONG_MAX;
    cin >> n >> k;
    vector<pair<long long,long long>> haha(0);
    for(long long i = 0; i < k; i++) {
        cin >> x >> y >> x >> y;
        haha.push_back({x-1,y-1});
    }
    for(long long i = 1; i < n; i++) {
        if(n%i == 0) {
            long long br = (((n/i)*(n/i)+1)/2)*i*i;
            for(long long j = 0; j < k; j++) {
                if((haha[j].first%(2*i) < i) == (haha[j].second%(2*i) < i)) {
                    br--;
                }
                else {
                    br++;
                }
            }
            ans = min(ans,br);
            br = (((n/i)*(n/i))/2)*i*i;
            for(long long j = 0; j < k; j++) {
                if((haha[j].first%(2*i) < i) != (haha[j].second%(2*i) < i)) {
                    br--;
                }
                else {
                    br++;
                }
            }
            ans = min(ans,br);
        }
    }
    cout << ans;
    return 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