Submission #336153

#	Time	Username	Problem	Language	Result	Execution time	Memory
336153		mat_v	Chessboard (IZhO18_chessboard)	C++14	100 / 100	581 ms	5996 KiB

chessboard

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx firsts
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define maxn 200005


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


int n;
int m;

struct kv{
    ll x1;
    ll y1;
    ll x2;
    ll y2;
}niz[maxn];

ll get(ll l, ll r, ll broj){
    if(l > r)return 0;
    ll prvi = (l/broj)*broj;
    if(l != prvi)prvi += broj;
    ll last = (r/broj)*broj;
    if(prvi > r){
        if((l%broj) < broj/2){
            return min((broj/2)-1, (r%broj))-(l%broj)+1;
        }
        return 0;
    }
    ll klk = last/broj - prvi/broj;
    return (klk)*(broj/2) + get(l,prvi-1,broj) + get(last+1,r,broj)+1;
}

int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;
    ff(i,1,m){
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        a--; b--; c--; d--;
        niz[i] = {a,b,c,d};
    }
    ll ans = 1e9;
    ans *= 10;
    ff(i,1,n - 1){
        if(n%i != 0)continue;
        ll b = 0;
        ll w = 0;
        ll tr = 2*i;
        ff(j,1,m){
            ll uk = 0;
            ll blackrow = get(niz[j].x1,niz[j].x2,tr);
            ll blackcol = get(niz[j].y1,niz[j].y2,tr);
            uk += (blackrow*blackcol);
            blackrow = niz[j].x2 - niz[j].x1 + 1 - blackrow;
            blackcol = niz[j].y2 - niz[j].y1 + 1 - blackcol;
            uk += (blackrow*blackcol);
            b += uk;
            w += ((niz[j].x2 - niz[j].x1 + 1) * (niz[j].y2 - niz[j].y1 + 1) - uk);
        }
        ll str = (n/i);
        ll p1 = (str*str + 1) / 2;
        ll p2 = (str*str) / 2;
        ll pomm = i;
        p1 *= (pomm*pomm);
        p2 *= (pomm*pomm);
        ll tmp = min(p1 - b + w, p2 - w + b);
        //cout << i << " " << tmp << "\n";
        ans = min(ans, tmp);
    }
    cout << ans << "\n";
    return 0;
}
/*
6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6
*/

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
chessboard.cpp:55:5: note: in expansion of macro 'ff'
   55 |     ff(i,1,m){
      |     ^~
chessboard.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
chessboard.cpp:63:5: note: in expansion of macro 'ff'
   63 |     ff(i,1,n - 1){
      |     ^~
chessboard.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
chessboard.cpp:68:9: note: in expansion of macro 'ff'
   68 |         ff(j,1,m){
      |         ^~

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