Submission #378546

#	Time	Username	Problem	Language	Result	Execution time	Memory
378546		balbit	Chessboard (IZhO18_chessboard)	C++14	0 / 100	45 ms	3820 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#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

#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);
            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
*/

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:39:15: warning: narrowing conversion of 'r2' from 'long long int' to 'int' [-Wnarrowing]
   39 |         v.pb({r2,c2,1});
      |               ^~
chessboard.cpp:39:18: warning: narrowing conversion of 'c2' from 'long long int' to 'int' [-Wnarrowing]
   39 |         v.pb({r2,c2,1});
      |                  ^~
chessboard.cpp:40:15: warning: narrowing conversion of 'r1' from 'long long int' to 'int' [-Wnarrowing]
   40 |         v.pb({r1,c1,1});
      |               ^~
chessboard.cpp:40:18: warning: narrowing conversion of 'c1' from 'long long int' to 'int' [-Wnarrowing]
   40 |         v.pb({r1,c1,1});
      |                  ^~
chessboard.cpp:41:15: warning: narrowing conversion of 'r2' from 'long long int' to 'int' [-Wnarrowing]
   41 |         v.pb({r2,c1,-1});
      |               ^~
chessboard.cpp:41:18: warning: narrowing conversion of 'c1' from 'long long int' to 'int' [-Wnarrowing]
   41 |         v.pb({r2,c1,-1});
      |                  ^~
chessboard.cpp:42:15: warning: narrowing conversion of 'r1' from 'long long int' to 'int' [-Wnarrowing]
   42 |         v.pb({r1,c2,-1});
      |               ^~
chessboard.cpp:42:18: warning: narrowing conversion of 'c2' from 'long long int' to 'int' [-Wnarrowing]
   42 |         v.pb({r1,c2,-1});
      |                  ^~

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