oj.uz

Submission #498025

# Submission time Handle Problem Language Result Execution time Memory
498025 2021-12-24T09:44:55 Z vinnipuh01 Chessboard (IZhO18_chessboard) C++17
8 / 100
 73 ms 2240 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;


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

int n, m;
int x[ 100001 ], y[ 100001 ], xx[ 100001 ], yy[ 100001 ];
	
int ff( int x, int y, int r ) {
	int sum, num, ans, mx;
	sum = x / r;
	num = ( sum + 1 ) / 2;
	num *= r;
	if ( sum % 2 == 0 )
		num += x % r;
	mx = y / r;
	ans = ( mx + 1 ) / 2;
	ans *= 2;
	if ( mx % 2 == 0 )
		ans += y % r;
	return ans * num + ( ( x - num ) * ( y - ans ) );
}

int f1( int x, int y, int  r ) {
	int sum, num, ans, mx;
	sum = x / r;
	num = ( sum + 1 ) / 2;
	num *= r;
	if ( sum % 2 == 0 )
		num += x % r;
	mx = y / r;
	ans = ( mx ) / 2;
	ans *= 2;
	if ( mx % 2 )
		ans += y % r;
	return ans * num + ( ( x - num ) * ( y - ans ) );
}
	
int f( int x1 ) {
	sum = ( n * n ) / ( x1 * x1 );
	ans = sum / 2;
	num = sum / 2;
	if ( sum % 2 )
		num ++;
	ans = ans * ( x1 * x1 );
	num = num * ( x1 * x1 );
	sum = 0;
	int mx = 0;
	for ( int i = 1; i <= m; i ++ ) {
		sum = ff( xx[ i ], yy[ i ], x1 ) + ff( x[ i ] - 1, y[ i ] - 1, x1 ) - ff( xx[ i ], y[ i ] - 1, x1 ) - ff( x[ i ] - 1, yy[ i ], x1 );
		mx = f1( xx[ i ], yy[ i ], x1 ) + f1( x[ i ] - 1, y[ i ] - 1, x1 ) - f1( xx[ i ], y[ i ] - 1, x1 ) - f1( x[ i ] - 1, yy[ i ], x1 );
//		cout << i << " - " << sum << " " << mx << "\n";
		ans += sum;
		ans -= mx;
		num += mx;
		num -= sum;
	}
//	cout << x1 << " " << ans << " " << num << "\n";
	return min( ans, num );
}

main () {
	cin >> n >> m;
	for ( int i = 1; i <= m; i ++ ) {
		cin >> x[ i ] >> y[ i ] >> xx[ i ] >> yy[ i ];
	}
	mn = f( 1 );
	int sqr = sqrt( n );
	for ( int i = 2; i <= sqr; i ++ ) {
		if ( n % i == 0 ) {
			mn = min( mn, min( f( i ), f( n / i ) ) );
		}
	}
	cout << mn;
}

/*
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

chessboard.cpp:102:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  102 | 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 1 ms 204 KB Output is correct
4 Correct 0 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 1 ms 204 KB Output is correct

Subtask #2
0 / 8.0

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

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 Incorrect 73 ms 2240 KB Output isn't correct
2 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 1 ms 204 KB Output is correct
4 Correct 0 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 1 ms 204 KB Output is correct
9 Incorrect 73 ms 2240 KB Output isn't correct
10 Halted 0 ms 0 KB -