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

926322 | 2024-02-12T19:23:05 Z | AlphaMale06 | Chessboard (IZhO18_chessboard) | C++14 | 291 ms | 5856 KB |

#include <bits/stdc++.h> using namespace std; #define F first #define S second #define int long long struct rect{ int x1, y1, x2, y2; }; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, k; cin >> n >> k; rect a[k]; for(int i=0; i< k; i++){ cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2; a[i].x1--; a[i].x2--; a[i].y1--; a[i].y2--; } int ans=1e12; for(int d=1; d<n; d++){ if(n%d!=0)continue; int flip=d*d*(((n*n)/(d*d)+1)/2); for(int i=0; i< k; i++){ int subx1=a[i].x1/d; int subx2=a[i].x2/d; int suby1=a[i].y1/d; int suby2=a[i].y2/d; if(subx1==subx2 && suby1==suby2){ if((subx1&1)==(suby1&1))flip-=(a[i].x2-a[i].x1+1)*(a[i].y2-a[i].y1+1); else flip+=(a[i].x2-a[i].x1+1)*(a[i].y2-a[i].y1+1); } else if(suby1==suby2){ int fali=(subx1+1)*d-1; int fali2=subx2*d; if((subx1&1)==(suby1&1))flip-=(a[i].y2-a[i].y1+1)*(fali-a[i].x1+1); else flip+=(a[i].y2-a[i].y1+1)*(fali-a[i].x1+1); if((subx2&1)==(suby1&1))flip-=(a[i].y2-a[i].y1+1)*(a[i].x2-fali2+1); else flip+=(a[i].y2-a[i].y1+1)*(a[i].x2-fali2+1); int dif=subx2-subx1-1; if(dif%2==0)continue; if((subx1&1)==(suby1&1))flip+=(a[i].y2-a[i].y1+1)*d; else flip-=(a[i].y2-a[i].y1+1)*d; } else if(subx1==subx2){ int fali=(suby1+1)*d-1; int fali2=suby2*d; if((suby1&1)==(subx1&1))flip-=(a[i].x2-a[i].x1+1)*(fali-a[i].y1+1); else flip+=(a[i].x2-a[i].x1+1)*(fali-a[i].y1+1); if((suby2&1)==(subx1&1))flip-=(a[i].x2-a[i].x1+1)*(a[i].y2-fali2+1); else flip+=(a[i].x2-a[i].x1+1)*(a[i].y2-fali2+1); int dif=suby2-suby1-1; if(dif%2==0)continue; if((suby1&1)==(subx1&1))flip+=(a[i].x2-a[i].x1+1)*d; else flip-=(a[i].x2-a[i].x1+1)*d; } else{ if(subx1%2==suby1%2)flip-=(subx1*d-a[i].x1)*(suby1*d-a[i].y1); else flip+=(subx1*d-a[i].x1)*(suby1*d-a[i].y1); if(subx1%2==suby2%2)flip-=(subx1*d-a[i].x1)*(a[i].y2-suby2*d+1); else flip+=(subx1*d-a[i].x1)*(a[i].y2-suby2*d+1); if(subx2%2==suby1%2)flip-=(a[i].x2-subx2*d+1)*(suby1*d-a[i].y1); else flip+=(a[i].x2-subx2*d+1)*(suby1*d-a[i].y1); if(subx2%2==suby2%2)flip-=(a[i].x2-subx2*d+1)*(a[i].y2-suby2*d+1); else flip+=(a[i].x2-subx2*d+1)*(a[i].y2-suby2*d+1); int difx=subx2-subx1-1; int dify=suby2-suby1-1; if(difx%2==0 && dify%2==0)continue; if(dify&1){ if(suby1%2==subx1%2)flip+=d*(subx1*d-a[i].x1); else flip-=d*(subx1*d-a[i].x1); if(suby1%2==subx2%2)flip+=d*(a[i].x2-subx2*d+1); else flip-=d*(a[i].x2-subx2*d+1); } if(difx&1){ if(subx1%2==suby1%2)flip+=d*(suby1*d-a[i].y1); else flip-=d*(suby1*d-a[i].y1); if(subx1%2==suby2%2)flip+=d*(a[i].y2-suby2*d+1); else flip-=d*(a[i].y2-suby2*d+1); } if(subx1%2==suby1%2)flip-=d*d; else flip+=d*d; } } ans=min({ans, flip, n*n-flip}); } cout << ans << '\n'; }

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

1 | Correct | 1 ms | 348 KB | Output is correct |

2 | Correct | 0 ms | 348 KB | Output is correct |

3 | Correct | 0 ms | 348 KB | Output is correct |

4 | Correct | 0 ms | 348 KB | Output is correct |

5 | Correct | 0 ms | 348 KB | Output is correct |

6 | Correct | 0 ms | 348 KB | Output is correct |

7 | Correct | 0 ms | 348 KB | Output is correct |

8 | Correct | 0 ms | 348 KB | Output is correct |

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

1 | Correct | 20 ms | 4440 KB | Output is correct |

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

3 | Correct | 11 ms | 2624 KB | Output is correct |

4 | Correct | 11 ms | 2636 KB | Output is correct |

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

6 | Correct | 10 ms | 2140 KB | Output is correct |

7 | Correct | 3 ms | 700 KB | Output is correct |

8 | Correct | 12 ms | 2140 KB | Output is correct |

9 | Correct | 25 ms | 5204 KB | Output is correct |

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

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

1 | Correct | 1 ms | 348 KB | Output is correct |

2 | Correct | 0 ms | 348 KB | Output is correct |

3 | Correct | 0 ms | 348 KB | Output is correct |

4 | Correct | 1 ms | 348 KB | Output is correct |

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

6 | Correct | 0 ms | 348 KB | Output is correct |

7 | Correct | 0 ms | 348 KB | Output is correct |

8 | Correct | 1 ms | 348 KB | Output is correct |

9 | Correct | 0 ms | 348 KB | Output is correct |

10 | Correct | 0 ms | 348 KB | Output is correct |

11 | Correct | 1 ms | 348 KB | Output is correct |

12 | Correct | 0 ms | 348 KB | Output is correct |

13 | Correct | 1 ms | 348 KB | Output is correct |

14 | Correct | 1 ms | 348 KB | Output is correct |

15 | Correct | 0 ms | 348 KB | Output is correct |

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

1 | Correct | 1 ms | 348 KB | Output is correct |

2 | Correct | 0 ms | 348 KB | Output is correct |

3 | Correct | 0 ms | 348 KB | Output is correct |

4 | Correct | 1 ms | 348 KB | Output is correct |

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

6 | Correct | 0 ms | 348 KB | Output is correct |

7 | Correct | 0 ms | 348 KB | Output is correct |

8 | Correct | 1 ms | 348 KB | Output is correct |

9 | Correct | 0 ms | 348 KB | Output is correct |

10 | Correct | 0 ms | 348 KB | Output is correct |

11 | Correct | 1 ms | 348 KB | Output is correct |

12 | Correct | 0 ms | 348 KB | Output is correct |

13 | Correct | 1 ms | 348 KB | Output is correct |

14 | Correct | 1 ms | 348 KB | Output is correct |

15 | Correct | 0 ms | 348 KB | Output is correct |

16 | Correct | 9 ms | 1748 KB | Output is correct |

17 | Correct | 22 ms | 4444 KB | Output is correct |

18 | Correct | 27 ms | 4948 KB | Output is correct |

19 | Correct | 64 ms | 4612 KB | Output is correct |

20 | Correct | 72 ms | 4952 KB | Output is correct |

21 | Correct | 18 ms | 4188 KB | Output is correct |

22 | Correct | 1 ms | 344 KB | Output is correct |

23 | Correct | 15 ms | 2396 KB | Output is correct |

24 | Correct | 24 ms | 4700 KB | Output is correct |

25 | Correct | 3 ms | 860 KB | Output is correct |

26 | Correct | 15 ms | 2976 KB | Output is correct |

27 | Correct | 21 ms | 3584 KB | Output is correct |

28 | Correct | 26 ms | 4956 KB | Output is correct |

29 | Correct | 8 ms | 1884 KB | Output is correct |

30 | Correct | 1 ms | 464 KB | Output is correct |

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

1 | Correct | 20 ms | 4440 KB | Output is correct |

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

3 | Correct | 11 ms | 2624 KB | Output is correct |

4 | Correct | 11 ms | 2636 KB | Output is correct |

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

6 | Correct | 10 ms | 2140 KB | Output is correct |

7 | Correct | 3 ms | 700 KB | Output is correct |

8 | Correct | 12 ms | 2140 KB | Output is correct |

9 | Correct | 25 ms | 5204 KB | Output is correct |

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

11 | Correct | 1 ms | 348 KB | Output is correct |

12 | Correct | 0 ms | 348 KB | Output is correct |

13 | Correct | 0 ms | 348 KB | Output is correct |

14 | Correct | 1 ms | 348 KB | Output is correct |

15 | Correct | 1 ms | 348 KB | Output is correct |

16 | Correct | 0 ms | 348 KB | Output is correct |

17 | Correct | 0 ms | 348 KB | Output is correct |

18 | Correct | 1 ms | 348 KB | Output is correct |

19 | Correct | 0 ms | 348 KB | Output is correct |

20 | Correct | 0 ms | 348 KB | Output is correct |

21 | Correct | 1 ms | 348 KB | Output is correct |

22 | Correct | 0 ms | 348 KB | Output is correct |

23 | Correct | 1 ms | 348 KB | Output is correct |

24 | Correct | 1 ms | 348 KB | Output is correct |

25 | Correct | 0 ms | 348 KB | Output is correct |

26 | Correct | 9 ms | 1748 KB | Output is correct |

27 | Correct | 22 ms | 4444 KB | Output is correct |

28 | Correct | 27 ms | 4948 KB | Output is correct |

29 | Correct | 64 ms | 4612 KB | Output is correct |

30 | Correct | 72 ms | 4952 KB | Output is correct |

31 | Correct | 18 ms | 4188 KB | Output is correct |

32 | Correct | 1 ms | 344 KB | Output is correct |

33 | Correct | 15 ms | 2396 KB | Output is correct |

34 | Correct | 24 ms | 4700 KB | Output is correct |

35 | Correct | 3 ms | 860 KB | Output is correct |

36 | Correct | 15 ms | 2976 KB | Output is correct |

37 | Correct | 21 ms | 3584 KB | Output is correct |

38 | Correct | 26 ms | 4956 KB | Output is correct |

39 | Correct | 8 ms | 1884 KB | Output is correct |

40 | Correct | 1 ms | 464 KB | Output is correct |

41 | Correct | 61 ms | 4816 KB | Output is correct |

42 | Correct | 30 ms | 5204 KB | Output is correct |

43 | Correct | 42 ms | 4976 KB | Output is correct |

44 | Correct | 28 ms | 5324 KB | Output is correct |

45 | Correct | 28 ms | 5796 KB | Output is correct |

46 | Correct | 74 ms | 5212 KB | Output is correct |

47 | Correct | 28 ms | 4960 KB | Output is correct |

48 | Correct | 35 ms | 5180 KB | Output is correct |

49 | Correct | 28 ms | 4688 KB | Output is correct |

50 | Correct | 264 ms | 5564 KB | Output is correct |

51 | Correct | 281 ms | 5760 KB | Output is correct |

52 | Correct | 262 ms | 5292 KB | Output is correct |

53 | Correct | 279 ms | 5484 KB | Output is correct |

54 | Correct | 261 ms | 5460 KB | Output is correct |

55 | Correct | 291 ms | 5856 KB | Output is correct |

56 | Correct | 253 ms | 4956 KB | Output is correct |

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

1 | Correct | 1 ms | 348 KB | Output is correct |

2 | Correct | 0 ms | 348 KB | Output is correct |

3 | Correct | 0 ms | 348 KB | Output is correct |

4 | Correct | 0 ms | 348 KB | Output is correct |

5 | Correct | 0 ms | 348 KB | Output is correct |

6 | Correct | 0 ms | 348 KB | Output is correct |

7 | Correct | 0 ms | 348 KB | Output is correct |

8 | Correct | 0 ms | 348 KB | Output is correct |

9 | Correct | 20 ms | 4440 KB | Output is correct |

10 | Correct | 5 ms | 1316 KB | Output is correct |

11 | Correct | 11 ms | 2624 KB | Output is correct |

12 | Correct | 11 ms | 2636 KB | Output is correct |

13 | Correct | 15 ms | 3448 KB | Output is correct |

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

15 | Correct | 3 ms | 700 KB | Output is correct |

16 | Correct | 12 ms | 2140 KB | Output is correct |

17 | Correct | 25 ms | 5204 KB | Output is correct |

18 | Correct | 14 ms | 3160 KB | Output is correct |

19 | Correct | 1 ms | 348 KB | Output is correct |

20 | Correct | 0 ms | 348 KB | Output is correct |

21 | Correct | 0 ms | 348 KB | Output is correct |

22 | Correct | 1 ms | 348 KB | Output is correct |

23 | Correct | 1 ms | 348 KB | Output is correct |

24 | Correct | 0 ms | 348 KB | Output is correct |

25 | Correct | 0 ms | 348 KB | Output is correct |

26 | Correct | 1 ms | 348 KB | Output is correct |

27 | Correct | 0 ms | 348 KB | Output is correct |

28 | Correct | 0 ms | 348 KB | Output is correct |

29 | Correct | 1 ms | 348 KB | Output is correct |

30 | Correct | 0 ms | 348 KB | Output is correct |

31 | Correct | 1 ms | 348 KB | Output is correct |

32 | Correct | 1 ms | 348 KB | Output is correct |

33 | Correct | 0 ms | 348 KB | Output is correct |

34 | Correct | 9 ms | 1748 KB | Output is correct |

35 | Correct | 22 ms | 4444 KB | Output is correct |

36 | Correct | 27 ms | 4948 KB | Output is correct |

37 | Correct | 64 ms | 4612 KB | Output is correct |

38 | Correct | 72 ms | 4952 KB | Output is correct |

39 | Correct | 18 ms | 4188 KB | Output is correct |

40 | Correct | 1 ms | 344 KB | Output is correct |

41 | Correct | 15 ms | 2396 KB | Output is correct |

42 | Correct | 24 ms | 4700 KB | Output is correct |

43 | Correct | 3 ms | 860 KB | Output is correct |

44 | Correct | 15 ms | 2976 KB | Output is correct |

45 | Correct | 21 ms | 3584 KB | Output is correct |

46 | Correct | 26 ms | 4956 KB | Output is correct |

47 | Correct | 8 ms | 1884 KB | Output is correct |

48 | Correct | 1 ms | 464 KB | Output is correct |

49 | Correct | 61 ms | 4816 KB | Output is correct |

50 | Correct | 30 ms | 5204 KB | Output is correct |

51 | Correct | 42 ms | 4976 KB | Output is correct |

52 | Correct | 28 ms | 5324 KB | Output is correct |

53 | Correct | 28 ms | 5796 KB | Output is correct |

54 | Correct | 74 ms | 5212 KB | Output is correct |

55 | Correct | 28 ms | 4960 KB | Output is correct |

56 | Correct | 35 ms | 5180 KB | Output is correct |

57 | Correct | 28 ms | 4688 KB | Output is correct |

58 | Correct | 264 ms | 5564 KB | Output is correct |

59 | Correct | 281 ms | 5760 KB | Output is correct |

60 | Correct | 262 ms | 5292 KB | Output is correct |

61 | Correct | 279 ms | 5484 KB | Output is correct |

62 | Correct | 261 ms | 5460 KB | Output is correct |

63 | Correct | 291 ms | 5856 KB | Output is correct |

64 | Correct | 253 ms | 4956 KB | Output is correct |

65 | Correct | 0 ms | 348 KB | Output is correct |

66 | Correct | 0 ms | 348 KB | Output is correct |

67 | Incorrect | 290 ms | 5532 KB | Output isn't correct |

68 | Halted | 0 ms | 0 KB | - |