oj.uz

Submission #52039

# Submission time Handle Problem Language Result Execution time Memory
52039 2018-06-23T10:47:48 Z mrtsima22 Chessboard (IZhO18_chessboard) C++17
8 / 100
 35 ms 1504 KB 
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int lmax=1999999999;
const long long lmx=1999999999999999999;
const int N=200004;
int n, k, x1[N], y11[N], x2[N], y2[N];
LL ans;
int pos;
 
 LL gety(LL y,LL she){
	if(y <= 0) return 0;
	LL res = (y / she) / 2 * she;
	if((y / she) & 1) res += y % she + 1;
	return res;
}
 
 LL getx(LL x,LL she){
	if(x <= 0) return 0;
	LL res = (x / she) / 2 * she;
	if((x / she) & 1) res += x % she + 1;
	return res;
}
 
void solve(int she){
	LL odd = 0, even = 0;
	for(int i = 1,xx,yy; i <= k; i++){
		LL o1 = gety(y2[i], she) - gety(y11[i] - 1, she);
		LL e1 = (y2[i] - y11[i] + 1) - o1;
		LL o2 = getx(x2[i], she) -  getx(x1[i] - 1, she); 
		LL e2 = (x2[i] - x1[i] + 1) - o2;
		xx = x1[i] / she;
		yy = y11[i] / she;
		if(xx & 1) swap(o1,e1);
		if(yy & 1) swap(o2,e2);
		LL od = 0, ev = 0;
		if((xx + yy) & 1){
			od = e1 * e2 + o1 * o2;
		}
		else{
		    od = o1 * e2 + e1 * o2;
		}
		ev = 1LL * (x2[i] - x1[i] + 1) * (y2[i] - y11[i] + 1) - od;
		
		odd += od;
		even += ev;
	}
	LL cnt = 1LL * (n / she) * (n / she);
	LL res = min(cnt / 2 * she * she + even - odd, (cnt + 1) / 2 * she * she + odd - even);
	if(res < ans){
	    pos = she;
		ans = res;
	}
}
int main(){std::ios::sync_with_stdio(false);
cin>>n>>k;
ans=1e18;
for(int i=1;i<=n;i++)
{
	cin>>x1[i]>>y11[i]>>x2[i]>>y2[i];
	x1[i]--;
	y11[i]--;
	x2[i]--;
	y2[i]--;
}
for(int i=1;i*i<=n;i++)
{
	if(n%i==0)
	{
		solve(i);
		if(i>1)
		{
			solve(n/i);
		}
	}
}
cout<<ans<<endl;
}
/*
                   *         *
                  * *       * *
                 *   *     *   *
                *     *   *     *
               *       * *       *
               *        *        *
                *               *
                 *             *
                  *           *
                   *         *
                    *       *
                     *     *
                      *   *
                       * *
                        * 
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 628 KB Output is correct
5 Correct 2 ms 628 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 23.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 628 KB Output is correct
5 Correct 2 ms 628 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Incorrect 35 ms 1504 KB Output isn't correct
10 Halted 0 ms 0 KB -