Submission #1130364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130364		harut_13	Chessboard (IZhO18_chessboard)	C++17	16 / 100	29 ms	1608 KiB

chessboard

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <map>
#include <string>
#include <ios>
#include <iomanip>
#include <deque>
#include <queue>
#include <list> 
#include <stack>

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(NULL);
#define CY   cout<<"YES"<<endl
#define CN   cout<<"NO"<<endl
#define ll   long long
#define ciN  cin
#define itn  int
#define pshb  push_back
#define sz  size()
#define vec vector<int>
#define vecl vector<long long>
#define fro for
#define Int int
#define stirng string
#define nedl   endl 
#define pi 3.141592653589793238463
#define endl '\n'
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MOD 1000000007


using namespace std;

ll gcd(ll n1, ll n2)
{
    if (n2 != 0)
        return gcd(n2, n1 % n2);
    else
        return n1;
}
ll lcm(ll a, ll b) {
    return a * b / (gcd(a, b));
}

ll pv(ll a, ll b) {
    if (b == 0)return 1;
    ll res = (pv(a, b / 2));
    if (b % 2) {
        return ((res) * (res) * (a));
    }
    else {
        return (res) * (res);
    }
}

void solve() {
    ll n; cin >> n;
    ll k; cin >> k;
    vector<pll> v(k);
    for (ll i = 0; i < k; i++) {
        ll a, b, c, d; cin >> a >> b >> c >> d;
        v[i] = { a,b };
    }
    vecl baj;
    for (ll i = 1; i < n; i++) {
        if (n % i == 0)baj.pshb(i);
    }
    sort(baj.begin(), baj.end());
    ll ans = n*n;
    for (ll i = 0; i < baj.sz; i++) {
        ll tv = baj[i];
        ll nerkum = tv * tv;
        ll x = n / tv;
        ll a, b;
        a = ((((x + 1) / 2) * ((x + 1) / 2))) + ((x / 2) * (x / 2));
        b = ((x / 2) * (x + 1) / 2) + (((x + 1) / 2) * (x / 2));
        a *= nerkum;
        b *= nerkum;
        for (ll j = 0; j < k; j++) {
            ll sharq = v[j].first;
            ll syun = v[j].second;
            ll sh = (sharq + tv - 1) / tv;
            ll sy = (syun + tv - 1) / tv;
            if (sh % 2 == 1) {
                if (sy % 2 == 1) {
                    a--;
                    b++;
                }
                else {
                    a++;
                    b--;
                }
            }
            else {
                if (sy % 2 == 1) {
                    a++;
                    b--;
                }
                else {
                    a--;
                    b++;
                }
            }
        }
        ans = min(ans,min(a,b));
    }
    cout << ans << endl;
}



signed main() { 
    FASTIO
        //int t; cin >> t;
    //while (t--)
        solve();


}

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