oj.uz

Submission #213341

# Submission time Handle Problem Language Result Execution time Memory
213341 2020-03-25T16:01:33 Z quocnguyen1012 Chessboard (IZhO18_chessboard) C++14
39 / 100
 191 ms 3584 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

int N, K;
vector<pair<ii, ii>> rect;
ll res = 1e18;

ll sub(int d, int x, int y)
{
  int X = x / d;
  int Y = y / d;
  ll ret = 0;
  if(X % 2 == 0 || Y % 2 == 0)
    ret += 1ll * X * Y / 2 * d * d;
  else
    ret += (1ll * X * Y / 2 + 1) * d * d;
  if (X % 2 == Y % 2) {
		ret += (ll) (x - X * d) * (y - Y * d);
	}
	if (Y % 2 == 0) {
		ret += (ll) (X + 1) / 2 * (y - Y * d) * d;
	}
	else {
		ret += (ll) X / 2 * (y - Y * d) * d;
	}
	if (X % 2 == 0) {
		ret += (ll) (Y + 1) / 2 * (x - X * d) * d;
	}
	else {
		ret += (ll) Y / 2 * (x - X * d) * d;
	}
	return ret;
}

ll solve(int d)
{
  ll sum = 0, rem = 0;
  for(auto & all : rect){
    sum += sub(d, all.se.fi, all.se.se) + sub(d, all.fi.fi - 1, all.fi.se - 1)
            - sub(d, all.fi.fi - 1, all.se.se) - sub(d, all.se.fi, all.fi.se - 1);
    rem += 1ll * (all.se.se - all.fi.se + 1) * (all.se.fi - all.fi.fi + 1);
  }
  ll black = sub(d, N, N);
  ll white = N * N - black;
  res = min(res, black + rem - 2 * sum);
  res = min(res, white - rem + 2 * sum);
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N >> K;
  rect.resize(K);
  for(auto & x : rect) cin >> x.fi.fi >> x.fi.se >> x.se.fi >> x.se.se;
  for(int i = 1; i < N; ++i){
    if(N % i == 0) solve(i);
  }
  cout << res;
}

Compilation message

chessboard.cpp: In function 'll solve(int)':
chessboard.cpp:56:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
8.0 / 8.0

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

Subtask #2
0 / 8.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 17 ms 1280 KB Output is correct
17 Correct 35 ms 3072 KB Output is correct
18 Correct 52 ms 3584 KB Output is correct
19 Correct 175 ms 3200 KB Output is correct
20 Correct 191 ms 3580 KB Output is correct
21 Correct 34 ms 2944 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 36 ms 1792 KB Output is correct
24 Correct 47 ms 3200 KB Output is correct
25 Correct 11 ms 640 KB Output is correct
26 Correct 33 ms 2176 KB Output is correct
27 Correct 48 ms 2560 KB Output is correct
28 Correct 50 ms 3456 KB Output is correct
29 Correct 17 ms 1408 KB Output is correct
30 Correct 6 ms 512 KB Output is correct

Subtask #5
0 / 23.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Incorrect 35 ms 2808 KB Output isn't correct
10 Halted 0 ms 0 KB -