# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

202244 | 2020-02-14T13:43:16 Z | ZwariowanyMarcin | Chessboard (IZhO18_chessboard) | C++14 | 873 ms | 4352 KB |

#include <bits/stdc++.h> #define LL long long #define pb push_back #define make_pair #define ss(x) (int) x.size() #define fi first #define se second #define cat(x) cerr << #x << " = " << x << endl using namespace std; const int nax = 1e5 + 11; const LL INF = 1e18; int n, k; LL best = INF; struct pt { int x, y, xx, yy; }; pt t[nax]; LL rec(int bok, int x, int y) { LL X = x / bok; LL Y = y / bok; LL black = 0; if (X % 2 == 0 || Y % 2 == 0) { black += (LL) X * Y / 2 * bok * bok; } else { black += (LL) ((X * Y) / 2 + 1) * bok * bok; } if (X % 2 == Y % 2) { black += (LL) (x - X * bok) * (y - Y * bok); } if (Y % 2 == 0) { black += (LL) (X + 1) / 2 * (y - Y * bok) * bok; } else { black += (LL) X / 2 * (y - Y * bok) * bok; } if (X % 2 == 0) { black += (LL) (Y + 1) / 2 * (x - X * bok) * bok; } else { black += (LL) Y / 2 * (x - X * bok) * bok; } return black; } void solve(int bok) { LL sum = 0; LL pole = 0; for (int i = 0; i < k; ++i) { sum += rec(bok, t[i].xx, t[i].yy) - rec(bok, t[i].x - 1, t[i].yy) - rec(bok, t[i].xx, t[i].y - 1) + rec(bok, t[i].x - 1, t[i].y - 1); pole += (LL) (t[i].xx - t[i].x + 1) * (t[i].yy - t[i].y + 1); } LL black = rec(bok, n, n); LL white = (LL) n * n - black; /*if (bok == 2) { cat(rec(2, t[0].x - 1, t[0].yy)); cat(black); cat(white); cat(sum); cat(pole); } */ best = min(best, (black - sum) + (pole - sum)); best = min(best, (white - (pole - sum)) + sum); } int main() { scanf ("%d%d", &n, &k); for (int i = 0; i < k; ++i) scanf ("%d %d %d %d", &t[i].x, &t[i].y, &t[i].xx, &t[i].yy); for (int i = 1; i < n; ++i) if (n % i == 0) solve(i); printf ("%lld", best); return 0; }

### Compilation message

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 5 ms | 256 KB | Output is correct |

2 | Correct | 5 ms | 256 KB | Output is correct |

3 | Correct | 5 ms | 256 KB | Output is correct |

4 | Correct | 5 ms | 256 KB | Output is correct |

5 | Correct | 5 ms | 376 KB | Output is correct |

6 | Correct | 5 ms | 256 KB | Output is correct |

7 | Correct | 5 ms | 380 KB | Output is correct |

8 | Correct | 5 ms | 256 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 39 ms | 1272 KB | Output is correct |

2 | Correct | 14 ms | 892 KB | Output is correct |

3 | Correct | 28 ms | 1912 KB | Output is correct |

4 | Correct | 27 ms | 1912 KB | Output is correct |

5 | Correct | 35 ms | 2468 KB | Output is correct |

6 | Correct | 24 ms | 1656 KB | Output is correct |

7 | Correct | 9 ms | 632 KB | Output is correct |

8 | Correct | 24 ms | 1656 KB | Output is correct |

9 | Correct | 55 ms | 3832 KB | Output is correct |

10 | Correct | 34 ms | 2296 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 5 ms | 256 KB | Output is correct |

2 | Correct | 5 ms | 256 KB | Output is correct |

3 | Correct | 5 ms | 256 KB | Output is correct |

4 | Correct | 5 ms | 248 KB | Output is correct |

5 | Correct | 5 ms | 376 KB | Output is correct |

6 | Correct | 5 ms | 256 KB | Output is correct |

7 | Correct | 5 ms | 376 KB | Output is correct |

8 | Correct | 5 ms | 376 KB | Output is correct |

9 | Correct | 5 ms | 376 KB | Output is correct |

10 | Correct | 7 ms | 256 KB | Output is correct |

11 | Correct | 5 ms | 380 KB | Output is correct |

12 | Correct | 5 ms | 256 KB | Output is correct |

13 | Correct | 5 ms | 376 KB | Output is correct |

14 | Correct | 5 ms | 376 KB | Output is correct |

15 | Correct | 5 ms | 376 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 5 ms | 256 KB | Output is correct |

2 | Correct | 5 ms | 256 KB | Output is correct |

3 | Correct | 5 ms | 256 KB | Output is correct |

4 | Correct | 5 ms | 248 KB | Output is correct |

5 | Correct | 5 ms | 376 KB | Output is correct |

6 | Correct | 5 ms | 256 KB | Output is correct |

7 | Correct | 5 ms | 376 KB | Output is correct |

8 | Correct | 5 ms | 376 KB | Output is correct |

9 | Correct | 5 ms | 376 KB | Output is correct |

10 | Correct | 7 ms | 256 KB | Output is correct |

11 | Correct | 5 ms | 380 KB | Output is correct |

12 | Correct | 5 ms | 256 KB | Output is correct |

13 | Correct | 5 ms | 376 KB | Output is correct |

14 | Correct | 5 ms | 376 KB | Output is correct |

15 | Correct | 5 ms | 376 KB | Output is correct |

16 | Correct | 21 ms | 760 KB | Output is correct |

17 | Correct | 45 ms | 1656 KB | Output is correct |

18 | Correct | 61 ms | 1912 KB | Output is correct |

19 | Correct | 182 ms | 1784 KB | Output is correct |

20 | Correct | 206 ms | 2008 KB | Output is correct |

21 | Correct | 41 ms | 1656 KB | Output is correct |

22 | Correct | 5 ms | 376 KB | Output is correct |

23 | Correct | 39 ms | 1016 KB | Output is correct |

24 | Correct | 56 ms | 1656 KB | Output is correct |

25 | Correct | 12 ms | 504 KB | Output is correct |

26 | Correct | 37 ms | 1144 KB | Output is correct |

27 | Correct | 52 ms | 1400 KB | Output is correct |

28 | Correct | 63 ms | 1784 KB | Output is correct |

29 | Correct | 19 ms | 888 KB | Output is correct |

30 | Correct | 6 ms | 376 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 39 ms | 1272 KB | Output is correct |

2 | Correct | 14 ms | 892 KB | Output is correct |

3 | Correct | 28 ms | 1912 KB | Output is correct |

4 | Correct | 27 ms | 1912 KB | Output is correct |

5 | Correct | 35 ms | 2468 KB | Output is correct |

6 | Correct | 24 ms | 1656 KB | Output is correct |

7 | Correct | 9 ms | 632 KB | Output is correct |

8 | Correct | 24 ms | 1656 KB | Output is correct |

9 | Correct | 55 ms | 3832 KB | Output is correct |

10 | Correct | 34 ms | 2296 KB | Output is correct |

11 | Correct | 5 ms | 256 KB | Output is correct |

12 | Correct | 5 ms | 256 KB | Output is correct |

13 | Correct | 5 ms | 256 KB | Output is correct |

14 | Correct | 5 ms | 248 KB | Output is correct |

15 | Correct | 5 ms | 376 KB | Output is correct |

16 | Correct | 5 ms | 256 KB | Output is correct |

17 | Correct | 5 ms | 376 KB | Output is correct |

18 | Correct | 5 ms | 376 KB | Output is correct |

19 | Correct | 5 ms | 376 KB | Output is correct |

20 | Correct | 7 ms | 256 KB | Output is correct |

21 | Correct | 5 ms | 380 KB | Output is correct |

22 | Correct | 5 ms | 256 KB | Output is correct |

23 | Correct | 5 ms | 376 KB | Output is correct |

24 | Correct | 5 ms | 376 KB | Output is correct |

25 | Correct | 5 ms | 376 KB | Output is correct |

26 | Correct | 21 ms | 760 KB | Output is correct |

27 | Correct | 45 ms | 1656 KB | Output is correct |

28 | Correct | 61 ms | 1912 KB | Output is correct |

29 | Correct | 182 ms | 1784 KB | Output is correct |

30 | Correct | 206 ms | 2008 KB | Output is correct |

31 | Correct | 41 ms | 1656 KB | Output is correct |

32 | Correct | 5 ms | 376 KB | Output is correct |

33 | Correct | 39 ms | 1016 KB | Output is correct |

34 | Correct | 56 ms | 1656 KB | Output is correct |

35 | Correct | 12 ms | 504 KB | Output is correct |

36 | Correct | 37 ms | 1144 KB | Output is correct |

37 | Correct | 52 ms | 1400 KB | Output is correct |

38 | Correct | 63 ms | 1784 KB | Output is correct |

39 | Correct | 19 ms | 888 KB | Output is correct |

40 | Correct | 6 ms | 376 KB | Output is correct |

41 | Correct | 167 ms | 3576 KB | Output is correct |

42 | Correct | 87 ms | 4088 KB | Output is correct |

43 | Correct | 107 ms | 3576 KB | Output is correct |

44 | Correct | 69 ms | 3960 KB | Output is correct |

45 | Correct | 61 ms | 4220 KB | Output is correct |

46 | Correct | 189 ms | 3960 KB | Output is correct |

47 | Correct | 55 ms | 3832 KB | Output is correct |

48 | Correct | 89 ms | 3832 KB | Output is correct |

49 | Correct | 65 ms | 3704 KB | Output is correct |

50 | Correct | 777 ms | 3960 KB | Output is correct |

51 | Correct | 841 ms | 4352 KB | Output is correct |

52 | Correct | 780 ms | 4104 KB | Output is correct |

53 | Correct | 830 ms | 4216 KB | Output is correct |

54 | Correct | 788 ms | 3832 KB | Output is correct |

55 | Correct | 862 ms | 4344 KB | Output is correct |

56 | Correct | 740 ms | 3816 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 5 ms | 256 KB | Output is correct |

2 | Correct | 5 ms | 256 KB | Output is correct |

3 | Correct | 5 ms | 256 KB | Output is correct |

4 | Correct | 5 ms | 256 KB | Output is correct |

5 | Correct | 5 ms | 376 KB | Output is correct |

6 | Correct | 5 ms | 256 KB | Output is correct |

7 | Correct | 5 ms | 380 KB | Output is correct |

8 | Correct | 5 ms | 256 KB | Output is correct |

9 | Correct | 39 ms | 1272 KB | Output is correct |

10 | Correct | 14 ms | 892 KB | Output is correct |

11 | Correct | 28 ms | 1912 KB | Output is correct |

12 | Correct | 27 ms | 1912 KB | Output is correct |

13 | Correct | 35 ms | 2468 KB | Output is correct |

14 | Correct | 24 ms | 1656 KB | Output is correct |

15 | Correct | 9 ms | 632 KB | Output is correct |

16 | Correct | 24 ms | 1656 KB | Output is correct |

17 | Correct | 55 ms | 3832 KB | Output is correct |

18 | Correct | 34 ms | 2296 KB | Output is correct |

19 | Correct | 5 ms | 256 KB | Output is correct |

20 | Correct | 5 ms | 256 KB | Output is correct |

21 | Correct | 5 ms | 256 KB | Output is correct |

22 | Correct | 5 ms | 248 KB | Output is correct |

23 | Correct | 5 ms | 376 KB | Output is correct |

24 | Correct | 5 ms | 256 KB | Output is correct |

25 | Correct | 5 ms | 376 KB | Output is correct |

26 | Correct | 5 ms | 376 KB | Output is correct |

27 | Correct | 5 ms | 376 KB | Output is correct |

28 | Correct | 7 ms | 256 KB | Output is correct |

29 | Correct | 5 ms | 380 KB | Output is correct |

30 | Correct | 5 ms | 256 KB | Output is correct |

31 | Correct | 5 ms | 376 KB | Output is correct |

32 | Correct | 5 ms | 376 KB | Output is correct |

33 | Correct | 5 ms | 376 KB | Output is correct |

34 | Correct | 21 ms | 760 KB | Output is correct |

35 | Correct | 45 ms | 1656 KB | Output is correct |

36 | Correct | 61 ms | 1912 KB | Output is correct |

37 | Correct | 182 ms | 1784 KB | Output is correct |

38 | Correct | 206 ms | 2008 KB | Output is correct |

39 | Correct | 41 ms | 1656 KB | Output is correct |

40 | Correct | 5 ms | 376 KB | Output is correct |

41 | Correct | 39 ms | 1016 KB | Output is correct |

42 | Correct | 56 ms | 1656 KB | Output is correct |

43 | Correct | 12 ms | 504 KB | Output is correct |

44 | Correct | 37 ms | 1144 KB | Output is correct |

45 | Correct | 52 ms | 1400 KB | Output is correct |

46 | Correct | 63 ms | 1784 KB | Output is correct |

47 | Correct | 19 ms | 888 KB | Output is correct |

48 | Correct | 6 ms | 376 KB | Output is correct |

49 | Correct | 167 ms | 3576 KB | Output is correct |

50 | Correct | 87 ms | 4088 KB | Output is correct |

51 | Correct | 107 ms | 3576 KB | Output is correct |

52 | Correct | 69 ms | 3960 KB | Output is correct |

53 | Correct | 61 ms | 4220 KB | Output is correct |

54 | Correct | 189 ms | 3960 KB | Output is correct |

55 | Correct | 55 ms | 3832 KB | Output is correct |

56 | Correct | 89 ms | 3832 KB | Output is correct |

57 | Correct | 65 ms | 3704 KB | Output is correct |

58 | Correct | 777 ms | 3960 KB | Output is correct |

59 | Correct | 841 ms | 4352 KB | Output is correct |

60 | Correct | 780 ms | 4104 KB | Output is correct |

61 | Correct | 830 ms | 4216 KB | Output is correct |

62 | Correct | 788 ms | 3832 KB | Output is correct |

63 | Correct | 862 ms | 4344 KB | Output is correct |

64 | Correct | 740 ms | 3816 KB | Output is correct |

65 | Correct | 5 ms | 376 KB | Output is correct |

66 | Correct | 5 ms | 256 KB | Output is correct |

67 | Correct | 819 ms | 4092 KB | Output is correct |

68 | Correct | 813 ms | 4088 KB | Output is correct |

69 | Correct | 713 ms | 3704 KB | Output is correct |

70 | Correct | 786 ms | 3952 KB | Output is correct |

71 | Correct | 781 ms | 3960 KB | Output is correct |

72 | Correct | 757 ms | 3832 KB | Output is correct |

73 | Correct | 749 ms | 3832 KB | Output is correct |

74 | Correct | 809 ms | 4088 KB | Output is correct |

75 | Correct | 781 ms | 3960 KB | Output is correct |

76 | Correct | 843 ms | 4216 KB | Output is correct |

77 | Correct | 161 ms | 4216 KB | Output is correct |

78 | Correct | 69 ms | 3832 KB | Output is correct |

79 | Correct | 110 ms | 3832 KB | Output is correct |

80 | Correct | 131 ms | 3832 KB | Output is correct |

81 | Correct | 108 ms | 3652 KB | Output is correct |

82 | Correct | 93 ms | 3960 KB | Output is correct |

83 | Correct | 79 ms | 3832 KB | Output is correct |

84 | Correct | 538 ms | 4092 KB | Output is correct |

85 | Correct | 862 ms | 4216 KB | Output is correct |

86 | Correct | 6 ms | 256 KB | Output is correct |

87 | Correct | 5 ms | 376 KB | Output is correct |

88 | Correct | 873 ms | 4216 KB | Output is correct |

89 | Correct | 171 ms | 1016 KB | Output is correct |

90 | Correct | 5 ms | 376 KB | Output is correct |