Submission #92888

#	Time	Username	Problem	Language	Result	Execution time	Memory
92888		muradeyn	Chessboard (IZhO18_chessboard)	C++14	70 / 100	1063 ms	4344 KiB

chessboard

/* Murad Eynizade */

#include <bits/stdc++.h>
#define intt long long
#define FAST_READ ios_base::sync_with_stdio(0);cin.tie(0);
#define SIZE 100001
#define INF INT_MAX
#define F first
#define S second
#define in(a) scanf("%d",&a);
#define outn(a) printf("%d\n",&a);
#define outs(a) printf("%d ",&a);

using namespace std;

struct rect{
    int a , b , c , d;
};

rect sub[SIZE];

intt need;

vector<intt>ans;

intt n , k;

vector<intt>dv;

int main()
{
    FAST_READ;
    cin>>n>>k;
    for (int i = 0;i<k;i++)cin>>sub[i].a>>sub[i].b>>sub[i].c>>sub[i].d;
    dv.push_back(1);
    for (int i = 2;i * i <= n;i++) {
        if (n % i == 0) {
            dv.push_back(i);
            if (i * i == n)continue;
            dv.push_back(n / i);
        }
    }
    for (intt i : dv) {
        need = ( (n / i + 1) / 2 ) * ( (n / i + 1) / 2 );
        need += (n / i / 2) * (n / i / 2);
        need *= (i * i);
        for (int j = 0;j < k;j++) {
            int row , column;
            if (sub[j].a % i == 0)row = sub[j].a / i;
            else row = (sub[j].a + i) / i;
            if (sub[j].b % i == 0)column = sub[j].b / i;
            else column = (sub[j].b + i) / i;
            if (row % 2 == column % 2) need--;
            else need++;
        }
        ans.push_back(need);
        need = n * n;
        need -= ( (n / i + 1) / 2 ) * ( (n / i + 1) / 2 ) * (i * i);
        need -= (n / i / 2) * (n / i / 2) * (i * i);
        for (int j = 0;j < k;j++) {
            int row , column;
            if (sub[j].a % i == 0)row = sub[j].a / i;
            else row = (sub[j].a + i) / i;
            if (sub[j].b % i == 0)column = sub[j].b / i;
            else column = (sub[j].b + i) / i;
            if (row % 2 == column % 2) need++;
            else need--;
        }
        ans.push_back(need);
    }
    sort(ans.begin(),ans.end());
    cout<<ans[0]<<endl;
    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