Submission #1211658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211658		adhityamv	Chessboard (IZhO18_chessboard)	C++20	70 / 100	164 ms	2004 KiB

chessboard

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <stack>
using namespace std;
#define int long long
#define mp make_pair
#define fi first
#define pii pair<int,int>
#define se second
const int INF=1000000000000000000;
//const int INF=1e9;
const int N=200000;
const int M=998244353;
const int ln=20;
template<typename T>
std::ostream& operator<< (std::ostream& os,pair<T,T> p){
    return os << p.fi << "," << p.se << " ";
}
struct segtree{
    vector<pii> seg;
    vector<int> lazy;
    segtree(int n){
        for(int i=0;i<4*n;i++){
            seg.push_back(mp(0,0));
            lazy.push_back(0);
        }
    }
void Build(int l,int r,int pos){
    if(l==r){
        seg[pos]=mp(l,-l);
        lazy[pos]=0;
        return;
    }
    int m=(l+r)/2;
    Build(l,m,2*pos);
    Build(m+1,r,2*pos+1);
    seg[pos]=min(seg[2*pos],seg[2*pos+1]);
}
void UpdateLazy(int l,int r,int pos){
    if(lazy[pos]==0) return;
    seg[pos].fi+=lazy[pos];
    if(l!=r){
        lazy[2*pos]+=lazy[pos];
        lazy[2*pos+1]+=lazy[pos];
    }
    lazy[pos]=0;
}
void Update(int l,int r,int pos,int ql,int qr,int val){
    UpdateLazy(l,r,pos);
    if(ql>r || qr<l) return;
    if(ql<=l && qr>=r){
        lazy[pos]+=val;
        UpdateLazy(l,r,pos);
        return;
    }
    int m=(l+r)/2;
    Update(l,m,2*pos,ql,qr,val);
    Update(m+1,r,2*pos+1,ql,qr,val);
    seg[pos]=min(seg[2*pos],seg[2*pos+1]);
}
pii Query(int l,int r,int pos,int ql,int qr){
    UpdateLazy(l,r,pos);
    if(ql>r || qr<l) return mp(INF,INF);
    if(ql<=l && qr>=r){
        return seg[pos];
    }
    int m=(l+r)/2;
    return min(Query(l,m,2*pos,ql,qr),Query(m+1,r,2*pos+1,ql,qr));
}
};
int f[N+1];
void solve(){
    int n,k;
    cin >> n >> k;
    vector<int> div;
    for(int i=1;i<n;i++){
        if(n%i==0) div.push_back(i);
    }
    pii pos[k];
    for(int i=0;i<k;i++){
        int xi,yi;
        int xj,yj;
        cin >> xi >> yi >> xj >> yj;
        xi--,yi--,xj--,yj--;
        assert(xi==xj && yi==yj);
        pos[i]=mp(xi,yi);
    }
    int mn=INF;
    for(int d:div){
        for(int cs=0;cs<2;cs++){
            int os;
            if((n/d)%2!=0){
                if(cs==0) os=(n*n+d*d)/2;
                else os=(n*n-d*d)/2;
            } else{
                os=(n*n)/2;
            }
            for(int i=0;i<k;i++){
                int i1=pos[i].fi/d;
                int i2=pos[i].se/d;
                if((i1+i2)%2==cs){
                    os--;
                } else os++;
            }
            mn=min(mn,os);
        }
    }
    cout << mn << "\n";
}
signed main(){
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t;
    //cin >> t;
    t=1;
    while(t--) solve();
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
}

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