Submission #521788

#	Time	Username	Problem	Language	Result	Execution time	Memory
521788		vonatlus	Chessboard (IZhO18_chessboard)	C++17	70 / 100	225 ms	2628 KiB

chessboard

/// adil sultanov | vonat1us 

#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:36777216")

#include<bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define sz(x) (int) x.size()
#define all(z) (z).begin(), (z).end()
 
using namespace std;

using ll = long long;
using pii = pair<int, int>;                                   

const int MOD = 1e9 + 7; 
const int INF = 1e9 + 1e2;
  
void fin() {
#ifdef AM
    freopen(".in", "r", stdin);
#endif        
}                   

const bool flag = 0;

const int N = 1e5+10;

void ma1n() {
    ll n, k;
    cin >> n >> k;
    vector<int> v;
    for (int i = 1; i <= sqrt(n); ++i) {
        if (n%i == 0) {
            v.pb(i);
            if (i*i != n) {
                v.pb(n/i);
            }
        }
    }
    sort(all(v));
    v.pop_back();
    vector<ll> res1(sz(v)), res2(sz(v));
    for (int i = 0; i < sz(v); ++i) {
        ll d = v[i];
        ll cnt = n/d;
        ll cnt1 = cnt/2;
        ll cnt2 = (cnt+1)/2;
        res1[i] = cnt1*cnt2*d*d*2;
        res2[i] = n*n - res1[i];
    }
    while (k--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--, b--, c--, d--;    
        for (int t = 0; t < sz(v); ++t) {
            int dv = v[t];
            int i = a/dv;
            int j = b/dv;
            if (i%2 != j%2) {
                res1[t]--;
                res2[t]++;
            } else {
                res1[t]++;
                res2[t]--;
            }
        }
    }
    ll ans = n*n;
    for (int i = 0; i < sz(v); ++i) {
        ans = min({ans, res1[i], res2[i]});    
    }
    cout << ans;
} 

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr), fin();
    int ts = 1;
    if (flag) {
        cin >> ts;
    }
    while (ts--) {
        ma1n(); 
    }
    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