oj.uz

Submission #495091

# Submission time Handle Problem Language Result Execution time Memory
495091 2021-12-18T04:43:18 Z vinnipuh01 Chessboard (IZhO18_chessboard) C++17
16 / 100
 109 ms 292 KB 
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int long long

using namespace std;

const long long oo = 1000000000000000000;

long long  sum, ans = 0, mx = 0, mn = 1000000000, num, pos, answer;


/*
    ViHHiPuh

   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))


    cout << fixed << setprecision(6) << x;

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    freopen ( "sum.in", "r", stdin )
*/

bool prime_number;
int n, m, x[ 100001 ], y[ 100001 ], xx[ 100001 ], yy[ 100001 ];


int f( int o ) {
	num = m * m;
	sum = o * o;
	mn = num / sum;
	ans = mn / 2;
	num = mn / 2;
	if ( mn % 2 )
		num ++;
	ans = ans * sum;
	num = num * sum;
	sum = mx = 0;
	for ( int i = 1; i <= n; i ++ ) {
		if ( ( x[ i ] + y[ i ] ) % 2 ) {
			sum ++;
			ans --;
		}
		else {
			num --;
			mx ++;
		}
	}
	return min( ans + mx, num + sum );
}

main () {
	cin >> m >> n;
	prime_number = 1;
	for ( int i = 2; i < m; i ++ ) {
		if ( m % i == 0 ) {
			prime_number = 0;
			break;
		}
	}
	num = m * m;
	ans = oo;
	for ( int i = 1; i < m; i ++ ) {
		if ( m % i == 0 ) {
			sum = i * i;
			mn = num / sum;
			mn = mn / 2;
			if ( ans > mn * sum ) {
				ans = mn * sum;
				pos = sum;
			}
		}
	}
	if ( !n || prime_number ) {
		if ( !n )
			cout << ans;
		else {
			num = ( num + 1 ) / 2;
			sum = mx = 0;
			int x, y, xx, yy;
			for ( int i = 1; i <= n; i ++ ) {
				cin >> x >> y >> xx >> yy;
				if ( ( x + y ) % 2 ) {
					sum ++;
					ans --;
				}
				else {
					mx ++;
					num --;
				}
			}
			cout << min( ans + mx, num + sum );
		}
	}
	else {
		for ( int i = 1; i <= n; i ++ ) {
			cin >> x[ i ] >> y[ i ] >> xx[ i ] >> yy[ i ];
			x[ i ] --;
			y[ i ] --;
			xx[ i ] --;
			yy[ i ] --;
		}
		answer = f( 1 );
		int sq = sqrt( m );
		for ( int i = 2; i <= sq; i ++ ) {
			if ( m % i == 0 ) {
				answer = min( answer, min( f( i ), f( m / i ) ) );
			}
		}
		cout << answer;
	}
}

Compilation message

chessboard.cpp:74:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   74 | main () {
      | ^~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 272 KB Output is correct
2 Correct 17 ms 204 KB Output is correct
3 Correct 42 ms 280 KB Output is correct
4 Correct 45 ms 272 KB Output is correct
5 Correct 54 ms 204 KB Output is correct
6 Correct 37 ms 204 KB Output is correct
7 Correct 8 ms 204 KB Output is correct
8 Correct 36 ms 292 KB Output is correct
9 Correct 109 ms 204 KB Output is correct
10 Correct 55 ms 276 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 272 KB Output is correct
2 Correct 17 ms 204 KB Output is correct
3 Correct 42 ms 280 KB Output is correct
4 Correct 45 ms 272 KB Output is correct
5 Correct 54 ms 204 KB Output is correct
6 Correct 37 ms 204 KB Output is correct
7 Correct 8 ms 204 KB Output is correct
8 Correct 36 ms 292 KB Output is correct
9 Correct 109 ms 204 KB Output is correct
10 Correct 55 ms 276 KB Output is correct
11 Incorrect 1 ms 204 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 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 61 ms 272 KB Output is correct
10 Correct 17 ms 204 KB Output is correct
11 Correct 42 ms 280 KB Output is correct
12 Correct 45 ms 272 KB Output is correct
13 Correct 54 ms 204 KB Output is correct
14 Correct 37 ms 204 KB Output is correct
15 Correct 8 ms 204 KB Output is correct
16 Correct 36 ms 292 KB Output is correct
17 Correct 109 ms 204 KB Output is correct
18 Correct 55 ms 276 KB Output is correct
19 Incorrect 1 ms 204 KB Output isn't correct
20 Halted 0 ms 0 KB -