Submission #343341

#	Time	Username	Problem	Language	Result	Execution time	Memory
343341		Sprdalo	Chessboard (IZhO18_chessboard)	C++17	70 / 100	601 ms	620 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

#define int ll
typedef unsigned long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

void no(){
    cout << "-1\n";
    exit(0);
}

vi d, b;
void calc(int x1, int x2, int y1, int y2, int ind){
    int t = d[ind], y = 0, Y = 0;

    if (y1/t == y2/t){
        if (y1%(2*t)<t)
            y = y2-y1+1;
        Y = y2-y1+1-y;
    } else {
        bool k1 = 0;
        if (y1%(2*t)<t){
            k1 = 1;
            y = t-y1;
        }

        bool k2 = 0;
        if (y2%(2*t)<t){
            k2 = 1;
            y += y2+1;
        }

        y += t * ((y2/t - y1/t - 1) / 2);
        if (!k1 && !k2)
            y += t;

        Y = y2-y1+1-y;
    }

    int x = 0, X = 0;
    if (x1/t == x2/t){
        if (x1 % (2*t) < t)
            x = x2-x1+1;
        X = x2-x1+1-x;
    } else {
        bool k1 = 0;
        if (x1%(2*t)<t){
            k1 = 1;
            x = t-x1;
        }

        bool k2 = 0;
        if (x2%(2*t)<t){
            k2 = 1;
            x += x2+1;
        }

        x += t * ((x2/t - x1/t - 1) / 2);
        if (!k1 && !k2)
            x += t;

        X = x2-x1+1-x;
    }

//    cout << x << ' ' << y << ' ' << X << ' ' << Y << '\n';

    b[ind] += x * y + X*Y;
}

signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    

    int n, k;
    cin >> n >> k;

    for (int i = 1; i < n; ++i){
        if (n % i == 0){
            d.push_back(i);
        }
    }

    int len = d.size(), s = 0;
    b = vi(len);
    for (int i = 0; i < k; ++i){
        int x1,y1,x2,y2;
        cin >> x1>>y1>>x2>>y2;

        --x1;
        --y1;
        --x2;
        --y2;
        s += (x2-x1+1) * (y2-y1+1);

        for (int j = 0; j < len; ++j)
        calc(x1,x2,y1,y2,j);
    }

    int sol = n*n;
    for (int i = 0; i < len; ++i){
        //cout << b[i] << ' ';
        int t = d[i],c;
        
        if (n % (2*t) == 0)
            c = (n*n)/2;
        else
            c = ((n-t)*(n-t))/2 + n*t;

        int res = s-b[i] + c-b[i];
        //cout << c << ' ';
        sol = min(sol, res);

        b[i] = s-b[i];

        c = n*n-c;

        res = s+c - 2 * b[i];
        //cout << c << endl;
        //cout << res << '\n';
        sol = min(sol, res);
    }

    cout << sol << '\n';
}

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