Submission #347025

#	Time	Username	Problem	Language	Result	Execution time	Memory
347025		andrii	Chessboard (IZhO18_chessboard)	C++14	100 / 100	1016 ms	15596 KiB

chessboard

// -- //
#include <bits/stdc++.h>
#define pll pair<ll, ll>
#define ppll pair<pll, pll>
#define x first
#define y second
using namespace std;
typedef long long ll;
const ll N = 1e5+228;
ppll a[N];
vector<pll> add[N], del[N];
ll res, n, k;
inline void ch(ll m) __attribute__((always_inline));
inline void ch(ll m){
    ll bob=0, bow=0;
    //wbw
    //bwb
    ll no[2]={0};
    bool fl=0;
    ll kk=0;
    for(ll i = 1;i<=n;i++, kk++){
        for(auto &j : add[i]){
            ll s = j.x, e = j.y;
            --s, e--;
            ll bs = s/m, be = e/m, bse = (bs+1)*m-1, bes = (be)*m;
            if(bs==be) no[bs&1] += e-s+1;
            else if(bs+1==be){
                no[bs&1] += bse-s+1;
                no[be&1] += e-bes+1;
            }else{
                no[bs&1] += bse-s+1;
                no[be&1] += e-bes+1;
                bs++, be--;
                ll kb = (be-bs+1)/2;
                no[bs&1] += (be-bs+1-kb)*m;
                no[(bs&1)^1] += kb*m;
            }
        }
        if(((i-1)/m)&1){
            bow+=no[0], bob+=no[1];
        }else{
            bob+=no[0], bow+=no[1];
        }
        for(auto &j : del[i]){
            ll s = j.x, e = j.y;
            --s, e--;
            ll bs = s/m, be = e/m, bse = (bs+1)*m-1, bes = (be)*m;
            if(bs==be) no[bs&1] -= e-s+1;
            else if(bs+1==be){
                no[bs&1] -= bse-s+1;
                no[be&1] -= e-bes+1;
            }else{
                no[bs&1] -= bse-s+1;
                no[be&1] -= e-bes+1;
                bs++, be--;
                ll kb = (be-bs+1)/2;
                no[bs&1] -= (be-bs+1-kb)*m;
                no[(bs&1)^1] -= kb*m;
            }
        }
    }
    ll bln = n/m;
    ll mbb = (bln/2)*m*n+((bln&1) ? (bln/2)+1 : 0)*m*m;
    ll v1 = (mbb-bob)+bow;
    ll v2 = bob+(n*n-mbb-bow);
    if(v1<res) res=v1;
    if(v2<res) res=v2;
}
signed main(){
	cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
    cin >> n >> k;
    for(ll i =0 ;i<k;i++){
        cin >> a[i].x.x >> a[i].x.y >> a[i].y.x >> a[i].y.y;
        add[a[i].x.y].push_back({a[i].x.x, a[i].y.x});
        del[a[i].y.y].push_back({a[i].x.x, a[i].y.x});
    }
    res=n*n;
    for(ll i = 1;i*i<=n;i++){
        if(n%i) continue;
        ch(i);
        if(i>1) ch(n/i);
    }
    cout<<res;
}

Compilation message (stderr)

chessboard.cpp: In function 'void ch(ll)':
chessboard.cpp:19:10: warning: unused variable 'fl' [-Wunused-variable]
   19 |     bool fl=0;
      |          ^~

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