Submission #343292

#	Time	Username	Problem	Language	Result	Execution time	Memory
343292		Sprdalo	Chessboard (IZhO18_chessboard)	C++17	70 / 100	255 ms	1004 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

#define int ll
typedef 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);
}

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

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

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

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

        if (x1!=x2 || y1 != y2)
            return 0;
        --x1;
        --y1;

        for (int j = 0; j < len; ++j){
            int t = d[j];

            bool b1 = (x1%(2*t) < t), b2 = (y1%(2*t) < t);
            if (b1 == b2){
                b[j]++;
            }
        }
    }

    int sol = n*n;
    for (int i = 0; i < len; ++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 = k-b[i] + c-b[i];
        //cout << c << ' ';
        sol = min(sol, res);

        b[i] = k-b[i];

        c = n*n-c;

        res = k+c - 2 * b[i];
        //cout << c << endl;
        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