oj.uz

Submission #857282

# Submission time Handle Problem Language Result Execution time Memory
857282 2023-10-05T19:37:57 Z NaimSS Chessboard (IZhO18_chessboard) C++14
16 / 100
 30 ms 5324 KB 
#include <bits/stdc++.h>
#include <iostream>
// #define int long long
#define ld long double
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define Unique(v) sort(all(v)),v.erase(unique(all(v)),v.end());
#define sz(v) ((int)v.size())
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
//#define left oooooopss
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
#define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
// std::mt19937_64 rng64((int) std::chrono::steady_clock::now().time_since_epoch().count());
std::mt19937 rng(
  
//  (int) std::chrono::steady_clock::now().time_since_epoch().count()
   1239010
);
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
//inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll b,ll e,ll m){
    b%=m;
    ll ans = 1;
    for (; e; b = b * b % m, e /= 2)
        if (e & 1) ans = ans * b % m;
    return ans;
}
// debug:
template<class T>void print_vector(vector<T> &v){
    rep(i,0,sz(v))cout<<v[i]<<" \n"[i==sz(v)-1];
}
void dbg_out() {cerr << endl; }
template<typename Head, typename ... Tail> void dbg_out(Head H,Tail... T){
    cerr << ' ' << H;
    dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__), cerr << endl
#else
#define dbg(...) 42
#endif
//
const int N = 100100;
ll x[N][2] , y[N][2];
int n,k;
ll solve(int d,int ini){
	ll L = n / d;
	ll totW = (L * L + 1)/2 * d * d;
	ll totB = (L*L)/2 * d * d;
	if(ini==1)swap(totW,totB);
	ll res = totB;
	auto add = [&](ll totW,ll totB,int inic){
		if(inic)swap(totW,totB);
		res -= totB;
		res += totW;
		return ;
	};
	rep(i,0,k){
		pll p1;
		if(x[i][0] % d != 0){
			p1.ff = x[i][0] + (d - x[i][0]);
		}else p1.ff = x[i][0];
		p1.ss = y[i][0] + (y[i][0]%d==0 ? 0 : d - (y[i][0]%d));
		pll p2;
		p2.ff = x[i][1] - (x[i][1]%d == d-1 ? 0 : (x[i][1]%d) + 1);
		p2.ss = y[i][1] - (y[i][1]%d == d-1 ? 0 : (y[i][1]%d) + 1);
		
		if(p1.ff <= p2.ff && p1.ss <= p2.ss){
			// all inside:
			ll l = (p2.ff - p1.ff + 1)/d;
			ll h = (p2.ss - p1.ss + 1)/d;
			int inic =(((p1.ff/d)+(p1.ss/d)) &1)^ini;
			ll totW = (l*h + 1)/2 * d * d;
			ll totB = (l*h)/2 * d * d;
			dbg(totW,totB);
			add(totW,totB,inic);
		}
		// upper:
		if(x[i][0] <= p1.ff - 1){
			int inic =(((x[i][0]/d)+(y[i][0]/d)) &1)^ini;
			ll l = (y[i][1] - y[i][0] + 1);
			ll h = (p1.ff-1 - x[i][0] + 1);
			ll totW = (l*h +1)/2;
			ll totB = (l*h)/2;
			add(totW,totB,inic);
		}
		// lower
		if(p2.ff + 1 <= x[i][1]){
			int inic = (((x[i][1]/d) + (y[i][1]/d))&1)^ini;
			ll l = (y[i][1] - y[i][0] + 1);
			ll h = (x[i][1] - (p2.ff + 1) + 1);
			ll totW = (l*h +1)/2;
			ll totB = (l*h)/2;
			add(totW,totB,inic);
		}
		// left:
		pll P1 = pll(p1.ff,y[i][0]), P2 = pll(p2.ff-1, p1.ss-1);
		if(P1.ff <= P2.ff && P1.ss <= P2.ss){
			int inic = ((P1.ff/d + P2.ff/d)& 1)^ini;
			ll l = P2.ff - P1.ff + 1;
			ll h = P2.ss - P1.ss + 1;
			ll totW = (l*h + 1)/2;
			ll totB = l*h/2;
			add(totW,totB,inic);
		}
		// right:
		P1 = pll(p2.ff, p2.ss + 1), P2 = pll(p2.ff-1,y[i][1]);
		if(P1.ff <= P2.ff && P1.ss <= P2.ss){
			int inic = ((P1.ff/d + P2.ff/d)& 1)^ini;
			ll l = P2.ff - P1.ff + 1;
			ll h = P2.ss - P1.ss + 1;
			ll totW = (l*h + 1)/2;
			ll totB = l*h/2;
			add(totW,totB,inic);
		}
	}
	dbg(d, ini , res);
	
	return res;
}

int32_t main(){
    fastio;
	cin >> n >> k;
	rep(i,0,k){
		rep(j,0,2)cin >> x[i][j] >> y[i][j];
	}
	ll res = n * (ll) n;
	for(int d=1;d < n;d++){
		if(n%d == 0){
			res = min(res, solve(d,0));
			res = min(res, solve(d,1));
		}
	}
	cout << res << endl;
	// math -> gcd it all
    // Did you swap N,M? N=1?
}

Compilation message

chessboard.cpp: In function 'll solve(int, int)':
chessboard.cpp:58:18: warning: statement has no effect [-Wunused-value]
   58 | #define dbg(...) 42
      |                  ^~
chessboard.cpp:93:4: note: in expansion of macro 'dbg'
   93 |    dbg(totW,totB);
      |    ^~~
chessboard.cpp:58:18: warning: statement has no effect [-Wunused-value]
   58 | #define dbg(...) 42
      |                  ^~
chessboard.cpp:135:2: note: in expansion of macro 'dbg'
  135 |  dbg(d, ini , res);
      |  ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4484 KB Output is correct
2 Correct 6 ms 2908 KB Output is correct
3 Correct 14 ms 3420 KB Output is correct
4 Correct 15 ms 3456 KB Output is correct
5 Correct 19 ms 4188 KB Output is correct
6 Correct 12 ms 3420 KB Output is correct
7 Correct 3 ms 2652 KB Output is correct
8 Correct 12 ms 3420 KB Output is correct
9 Correct 30 ms 5324 KB Output is correct
10 Correct 17 ms 3932 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2508 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 2508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4484 KB Output is correct
2 Correct 6 ms 2908 KB Output is correct
3 Correct 14 ms 3420 KB Output is correct
4 Correct 15 ms 3456 KB Output is correct
5 Correct 19 ms 4188 KB Output is correct
6 Correct 12 ms 3420 KB Output is correct
7 Correct 3 ms 2652 KB Output is correct
8 Correct 12 ms 3420 KB Output is correct
9 Correct 30 ms 5324 KB Output is correct
10 Correct 17 ms 3932 KB Output is correct
11 Incorrect 1 ms 2508 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 27 ms 4484 KB Output is correct
10 Correct 6 ms 2908 KB Output is correct
11 Correct 14 ms 3420 KB Output is correct
12 Correct 15 ms 3456 KB Output is correct
13 Correct 19 ms 4188 KB Output is correct
14 Correct 12 ms 3420 KB Output is correct
15 Correct 3 ms 2652 KB Output is correct
16 Correct 12 ms 3420 KB Output is correct
17 Correct 30 ms 5324 KB Output is correct
18 Correct 17 ms 3932 KB Output is correct
19 Incorrect 1 ms 2508 KB Output isn't correct
20 Halted 0 ms 0 KB -