Submission #495527

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
495527	2021-12-19T09:19:42 Z	AQ0212	Chessboard (IZhO18_chessboard)	C++17	Compilation error	0 ms	0 KB

chessboard

#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <sstream>
#include <cstring>

#define int long long int
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define all(x) x.begin(), x.end()

using namespace std;

int inf2 = 3e18;

int x1[ 100111 ], x2[ 100111 ];
int y11[ 100111 ], y2[ 100111 ], ans = inf2;
vector < int > divv;
map < int , int > mp;

int white_first(int sz, int n, int m){
	int sqrs = n / sz;
	int cnt_move = (sqrs & 1) ? ((((sqrs >> 1) * ((sqrs >> 1) + 1)) << 1) * (sz * sz)) : (sqrs >> 1) * (sqrs) * (sz * sz);
	// cout << "w: " << cnt_move << " sz: " << sz << "\n";

	for(int i = 1; i <= m; i ++){
		if(x1[ i ] == x2[ i ] && y11[ i ] == y2[ i ]){
			if(((x1[ i ] + sz - 1) / sz) & 1)
				if(((y11[ i ] + sz - 1) / sz) & 1)
					cnt_move ++;
				else
					cnt_move --;
			else
				if(((y11[ i ] + sz - 1) / sz) & 1)
					cnt_move --;
				else
					cnt_move ++;
			continue;
		}
		for(int j = 1, j2 = 1; j <= n; j += sz, j2 ++){

			if(j <= x1[ i ] && x2[ i ] <= (j2 * sz)){
				for(int k = 1, k2 = 1; k <= n; k += sz, k2 ++){

					if(k <= y11[ i ] && y2[ i ] <= (k2 * sz)){
						if(j2 & 1)
							if(k2 & 1)
								cnt_move += (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
							else
								cnt_move -= (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
						else
							if(k2 & 1)
								cnt_move -= (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
							else
								cnt_move += (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
						break;
					}else if(k <= y11[ i ] && y11[ i ] <= (k2 * sz) && (k2 * sz) <= y2[ i ]){
						if(j2 & 1)
							if(k2 & 1)
								cnt_move += (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
							else
								cnt_move -= (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
						else
							if(k2 & 1)
								cnt_move -= (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
							else
								cnt_move += (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);

					}else if(y11[ i ] <= k && (k2 * sz) <= y2[ i ]){
						if(j2 & 1)
							if(k2 & 1)
								cnt_move += (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - k + 1);
							else
								cnt_move -= (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - k + 1);
						else
							if(k2 & 1)
								cnt_move -= (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - k + 1);
							else
								cnt_move += (x2[ i ] - x1[ i ] + 1) * ((k2 * sz) - k + 1);

					}else{
						if(j2 & 1)
							if(k2 & 1)
								cnt_move += (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - k + 1);
							else
								cnt_move -= (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - k + 1);
						else
							if(k2 & 1)
								cnt_move -= (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - k + 1);
							else
								cnt_move += (x2[ i ] - x1[ i ] + 1) * (y2[ i ] - k + 1);
						// break;
					}
				}

			}else if(j <= x1[ i ] && x1[ i ] <= (j2 * sz) && (j2 * sz) <= x2[ i ]){
				for(int k = 1, k2 = 1; k <= n; k += sz, k2 ++){

					if(k <= y11[ i ] && y2[ i ] <= (k2 * sz)){
						if(j2 & 1)
							if(k2 & 1)
								cnt_move += ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
							else
								cnt_move -= ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
						else
							if(k2 & 1)
								cnt_move -= ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
							else
								cnt_move += ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - y11[ i ] + 1);
						break;
					}else if(k <= y11[ i ] && y11[ i ] <= (k2 * sz) && (k2 * sz) <= y2[ i ]){
						if(j2 & 1)
							if(k2 & 1)
								cnt_move += ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
							else
								cnt_move -= ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
						else
							if(k2 & 1)
								cnt_move -= ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);
							else
								cnt_move += ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - y11[ i ] + 1);

					}else if(y11[ i ] <= k && (k2 * sz) <= y2[ i ]){
						if(j2 & 1)
							if(k2 & 1)
								cnt_move += ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - k + 1);
							else
								cnt_move -= ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - k + 1);
						else
							if(k2 & 1)
								cnt_move -= ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - k + 1);
							else
								cnt_move += ((j2 * sz) - x1[ i ] + 1) * ((k2 * sz) - k + 1);

					}else{
						if(j2 & 1)
							if(k2 & 1)
								cnt_move += ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - k + 1);
							else
								cnt_move -= ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - k + 1);
						else
							if(k2 & 1)
								cnt_move -= ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - k + 1);
							else
								cnt_move += ((j2 * sz) - x1[ i ] + 1) * (y2[ i ] - k + 1);
						// break;
					}
				}

			}else if(x1[ i ] <= j && (j2 * sz) <= x2[ i ]){
				for(int k = 1, k2 = 1; k <= n; k += sz, k2 ++){

					if(k <= y11[ i ] && y2[ i ] <= (k2 * sz)){
						if(j2 & 1)
							if(k2 & 1)
								cnt_move += ((j2 * sz) - j + 1) * (y2[ i ] - y11[ i ] + 1);
							else
								cnt_move -= ((j2 * sz) - j + 1) * (y2[ i ] - y11[ i ] + 1);
						else
							if(k2 & 1)
								cnt_move -= ((j2 * sz) - j + 1) * (y2[ i ] - y11[ i ] + 1);
							else
								cnt_move += ((j2 * sz) - j + 1) * (y2[ i ] - y11[ i ] + 1);
						break;
					}else if(k <= y11[ i ] && y11[ i ] <= (k2 * sz) && (k2 * sz) <= y2[ i ]){
						if(j2 & 1)
							if(k2 & 1)
								cnt_move += ((j2 * sz) - j + 1) * ((k2 * sz) - y11[ i ] + 1);
							else
								cnt_move -= ((j2 * sz) - j + 1) * ((k2 * sz) - y11[ i ] + 1);
						else
							if(k2 & 1)
								cnt_move -= ((j2 * sz) - j + 1) * ((k2 * sz) - y11[ i ] + 1);
							else
								cnt_move += ((j2 * sz) - j + 1) * ((k2 * sz) - y11[ i ] + 1);

					}else if(y11[ i ] <= k && (k2 * sz) <= y2[ i ]){
						if(j2 & 1)
							if(k2 & 1)
								cnt_move += ((j2 * sz) - j + 1) * ((k2 * sz) - k + 1);
							else
								cnt_move -= ((j2 * sz) - j + 1) * ((k2 * sz) - k + 1);
						else
							if(k2 & 1)
								cnt_move -= ((j2 * sz) - j + 1) * ((k2 * sz) - k + 1);
							else
								cnt_move += ((j2 * sz) - j + 1) * ((k2 * sz) - k + 1);

					}else{
						if(j2 & 1)
							if(k2 & 1)
								cnt_move += ((j2 * sz) - j + 1) * (y2[ i ] - k + 1);
							else
								cnt_move -= ((j2 * sz) - j + 1) * (y2[ i ] - k + 1);
						else
							if(k2 & 1)
								cnt_move -= ((j2 * sz) - j + 1) * (y2[ i ] - k + 1);
							else
								cnt_move += ((j2 * sz) - j + 1) * (y2[ i ] - k + 1);
						// break;
					}
				}

			}else{
				for(int k = 1, k2 = 1; k <= n; k += sz, k2 ++){

					if(k <= y11[ i ] && y2[ i ] <= (k2 * sz)){
						if(j2 & 1)
							if(k2 & 1)
								cnt_move += (x2[ i ] - j + 1) * (y2[ i ] - y11[ i ] + 1);
							else
								cnt_move -= (x2[ i ] - j + 1) * (y2[ i ] - y11[ i ] + 1);
						else
							if(k2 & 1)
								cnt_move -= (x2[ i ] - j + 1) * (y2[ i ] - y11[ i ] + 1);
							else
								cnt_move += (x2[ i ] - j + 1) * (y2[ i ] - y11[ i ] + 1);
						break;
					}else if(k <= y11[ i ] && y11[ i ] <= (k2 * sz) && (k2 * sz) <= y2[ i ]){
						if(j2 & 1)
							if(k2 & 1)
								cnt_move += (x2[ i ] - j + 1) * ((k2 * sz) - y11[ i ] + 1);
							else
								cnt_move -= (x2[ i ] - j + 1) * ((k2 * sz) - y11[ i ] + 1);
						else
							if(k2 & 1)
								cnt_move -= (x2[ i ] - j + 1) * ((k2 * sz) - y11[ i ] + 1);
							else
								cnt_move += (x2[ i ] - j + 1) * ((k2 * sz) - y11[ i ] + 1);

					}else if(y11[ i ] <= k && (k2 * sz) <= y2[ i ]){
						if(j2 & 1)
							if(k2 & 1)
								cnt_move += (x2[ i ] - j + 1) * ((k2 * sz) - k + 1);
							else
								cnt_move -= (x2[ i ] - j + 1) * ((k2 * sz) - k + 1);
						else
							if(k2 & 1)
								cnt_move -= (x2[ i ] - j + 1) * ((k2 * sz) - k + 1);
							else
								cnt_move += (x2[ i ] - j + 1) * ((k2 * sz) - k + 1);

					}else{
						if(j2 & 1)
							if(k2 & 1)
								cnt_move += (x2[ i ] - j + 1) * (y2[ i ] - k + 1);
							else
								cnt_move -= (x2[ i ] - j + 1) * (y2[ i ] - k + 1);
						else
							if(k2 & 1)
								cnt_move -= (x2[ i ] - j + 1) * (y2[ i ] - k + 1);
							else
								cnt_move += (x2[ i ] - j + 1) * (y2[ i ] - k + 1);
						// break;
					}
				}

			}
		}
	}

	return cnt_move;
}

int main(){
	int n, m;

	cin >> n >> m;

	for(int i = 1; i <= m; i ++){
		scanf("%d%d%d%d", &x1[ i ], &y11[ i ], &x2[ i ], &y2[ i ]);
	}

	divv.pb(1);
	for(int i = 2; i <= ((int)ceil(sqrt(n))); i ++){
		if(n % i == 0 && !mp[ i ] && i != n){
			divv.pb(i);
			mp[ i ] ++;
			if(!mp[ n / i ]){
				divv.pb(n / i);
				mp[ n / i ] ++;
			}
		}
	}

	sort(all(divv));

	for(int i = 0; i < divv.size(); i ++){
		int white = white_first(divv[ i ], n, m);
		
		ans = min(ans, min((n * n) - white, white));
		// cout << white << " " << (n * n) - white << "\n";
	}

	cout << ans;
}

Compilation message

chessboard.cpp:11:23: error: '::main' must return 'int'
   11 | #define int long long int
      |                       ^~~
chessboard.cpp:271:1: note: in expansion of macro 'int'
  271 | int main(){
      | ^~~
chessboard.cpp: In function 'int main()':
chessboard.cpp:277:11: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  277 |   scanf("%d%d%d%d", &x1[ i ], &y11[ i ], &x2[ i ], &y2[ i ]);
      |          ~^         ~~~~~~~~
      |           |         |
      |           int*      long long int*
      |          %lld
chessboard.cpp:277:13: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
  277 |   scanf("%d%d%d%d", &x1[ i ], &y11[ i ], &x2[ i ], &y2[ i ]);
      |            ~^                 ~~~~~~~~~
      |             |                 |
      |             int*              long long int*
      |            %lld
chessboard.cpp:277:15: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
  277 |   scanf("%d%d%d%d", &x1[ i ], &y11[ i ], &x2[ i ], &y2[ i ]);
      |              ~^                          ~~~~~~~~
      |               |                          |
      |               int*                       long long int*
      |              %lld
chessboard.cpp:277:17: warning: format '%d' expects argument of type 'int*', but argument 5 has type 'long long int*' [-Wformat=]
  277 |   scanf("%d%d%d%d", &x1[ i ], &y11[ i ], &x2[ i ], &y2[ i ]);
      |                ~^                                  ~~~~~~~~
      |                 |                                  |
      |                 int*                               long long int*
      |                %lld
chessboard.cpp:294:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  294 |  for(int i = 0; i < divv.size(); i ++){
      |                 ~~^~~~~~~~~~~~~
chessboard.cpp:277:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  277 |   scanf("%d%d%d%d", &x1[ i ], &y11[ i ], &x2[ i ], &y2[ i ]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~