제출 #1130360

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130360		harut_13	Chessboard (IZhO18_chessboard)	C++20	16 / 100	29 ms	1096 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);
    }
}
struct dub {
    int x;
    int y;
};
void solve(){
    ll n; cin >> n;
    ll k; cin >> k;
    if (k == 0) {
        ll ans = 1e9;
        for (int i = 1; i < n; i++) {
            if (n % i == 0) {
                ll nerkum = i * i;
                ll x = n / i;
                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);
                ans = min({ ans,a * nerkum,b * nerkum });
            }
        }
        cout << ans << endl;
    }
    else {
        vector<dub> v(k);
        for (int i = 0; i < k; i++) {
            int a, b, c, d; cin >> a >> b >> c >> d;
            v[i] = {a,b};
        }
        ll a = ((n / 2) * (n + 1) / 2) + (((n + 1) / 2) * (n / 2));
        ll b = (((n + 1) / 2) * ((n + 1) / 2)) + ((n / 2) * (n / 2));
        for (int i = 0; i < k; i++) {
            if (v[i].x % 2 == 0) {
                if (v[i].y % 2 == 0) {
                    a++;
                    b--;
                }
                else {
                    b++;
                    a--;
                }
            }
            else {
                if (v[i].y % 2 == 0) {
                    a--;
                    b++;
                }
                else {
                    b--;
                    a++;
                }
            }
        }
        cout << min({ a,b });
    }
}
void solve1() {
    ll n; cin >> n;
    ll k; cin >> k;
    vector<dub> v(k);
    for (int i = 0; i < k; i++) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        v[i] = { a,b };
    }
    vec 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 (int 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 (int j = 0; j < k; j++) {
            ll sharq = v[j].x;
            ll syun = v[j].y;
            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,a,b });
    }
    cout << ans << endl;
}



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


}

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