oj.uz

Submission #378564

# Submission time Handle Problem Language Result Execution time Memory
378564 2021-03-17T01:47:53 Z balbit Chessboard (IZhO18_chessboard) C++14
0 / 100
 41 ms 7148 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define int ll
#define f first
#define s second
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define pii pair<int, int>
#define SZ(x) (int)((x).size())
#define ALL(x) x.begin(), x.end()
#define pb push_back
#define MX(a,b) a = max(a,b)

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

struct rect{
    int x,y,d;
};

int ps[2][100005];

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    bug(1,2);
    int n,k; cin>>n>>k;
    vector<rect> v; v.reserve(k*4);
    ll rr = 0;
    REP(i,k) {
        ll r1,c1,r2,c2; cin>>r1>>c1>>r2>>c2;
        rr += (r2-r1+1) * (c2-c1+1);
        --r1; --c1; --r2; --c2; --r1; --c1;
        v.pb({r2,c2,1});
        v.pb({r1,c1,1});
        v.pb({r2,c1,-1});
        v.pb({r1,c2,-1});
    }
    ll re = 1e18;
    for (int d = 1; d<n; ++d) {
        if (n % d == 0) {
            ll totb = (n*n + ((n/d)&1?d*d:0))/2;
            REP1(i,n) {
                if (i) ps[0][i] = ps[0][i-1];
                ps[0][i] += ((i-1)/d)%2==0;
                ps[1][i] = i-ps[0][i];
            }
            bug(d, totb);
            int over = 0;
            for (rect r : v) {
                if (r.x>=0&&r.y>=0) {
                    int tmp = 0;
                    ++r.x; ++r.y;
                    tmp += (r.x%d) * (ps[((r.x-1)/d)&1][r.y]);
                    tmp += (r.y%d) * (ps[((r.y-1)/d)&1][r.x-r.x%d]);
                    r.x -= r.x%d; r.y -= r.y%d;
//                    --r.x; --r.y;
                    if (((r.x/d)&1) && ((r.y/d)&1)) {
                        tmp += ((r.x*r.y)+d*d)/2;
                    }else{
                        tmp += r.x*r.y/2;
                    }
                    over += tmp * r.d;
                }
            }
            bug(over);
            bug(totb + rr - over*2);
            MX(over, rr-over);
            re = min(re, totb + rr - over*2);
        }
    }
    cout<<re<<endl;
}

/*
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
*/

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 7148 KB Output is correct
2 Incorrect 12 ms 2156 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 7148 KB Output is correct
2 Incorrect 12 ms 2156 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -