oj.uz

Submission #747092

# Submission time Handle Problem Language Result Execution time Memory
747092 2023-05-23T15:42:03 Z heeheeheehaaw Chessboard (IZhO18_chessboard) C++17
70 / 100
 463 ms 5452 KB 
#include <iostream>
#include <vector>
#define int long long

using namespace std;

int a[1005][1005];
int spw[1005][1005], spb[1005][1005];
int x1[100005], x2[100005], y1[100005], y2[100005];

void add(int x, int y, int val, int &s1, int &s2)
{
    if((x + y) % 2 == 0)
        s1 += val;
    else
        s2 += val;
    return;
}

signed main()
{
    int s1 = 0, s2 = 0;
    int n, k;
    cin>>n>>k;

    vector<int> divs;
    for(int i = 1; i * i <= n; i++)
        if(n % i == 0)
        {
            divs.push_back(i);
            if(i * i != n && i != 1)
                divs.push_back(n / i);
        }

    for(int i = 1; i <= k; i++)
        cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];

    int minn = n * n;
    for(auto d : divs)
    {
        int s1 = 0, s2 = 0;
        for(int i = 1; i <= k; i++)
        {
            int cx1 = (x1[i] - 1) / d + 1;
            int cy1 = (y1[i] - 1) / d + 1;
            int cx2 = (x2[i] - 1) / d + 1;
            int cy2 = (y2[i] - 1) / d + 1;

            if(cx1 == cx2 && cy1 == cy2)
            {
                int tt = (x2[i] - x1[i] + 1) * (y2[i] - y1[i] + 1);
                add(cx1, cy1, tt, s1, s2);
            }
            else if(cx1 == cx2 && cy1 != cy2)
            {
                /// colt stanga
                int tt = ((d * cy1) - y1[i] + 1) * (x2[i] - x1[i] + 1);
                add(cx1, cy1, tt, s1, s2);
                /// colt dreapta
                    tt = (y2[i] - d * (cy2 - 1)) * (x2[i] - x1[i] + 1);
                add(cx2, cy2, tt, s1, s2);
                /// mijloc
                if(cy2 - cy1 - 1 >= 1)
                {
                    int tt = d * (x2[i] - x1[i] + 1);
                    int np = cy2 - cy1 - 1;
                    int nri = np / 2, nrp = np / 2;
                    if(np % 2 == 1)
                        nri++;
                    add(cx1, cy1 + 1, tt * nri, s1, s2);
                    add(cx1, cy1 + 2, tt * nrp, s1, s2);
                }
            }
            else if(cx1 != cx2 && cy1 == cy2)
            {
                /// colt sus
                int tt = ((d * cx1) - x1[i] + 1) * (y2[i] - y1[i] + 1);
                add(cx1, cy1, tt, s1, s2);
                /// colt jos
                    tt = (x2[i] - d * (cx2 - 1)) * (y2[i] - y1[i] + 1);
                add(cx2, cy2, tt, s1, s2);
                /// mijloc
                if(cx2 - cx1 - 1 >= 1)
                {
                    int tt = d * (y2[i] - y1[i] + 1);
                    int np = cx2 - cx1 - 1;
                    int nri = np / 2, nrp = np / 2;
                    if(np % 2 == 1)
                        nri++;
                    add(cx1 + 1, cy1, tt * nri, s1, s2);
                    add(cx1 + 2, cy1, tt * nrp, s1, s2);
                }
            }
            else
            {
                /// colt st sus
                int tt = (d * cx1 - x1[i] + 1) * (d * cy1 - y1[i] + 1);
                add(cx1, cy1, tt, s1, s2);
                /// colt dr sus
                    tt = (d * cx1 - x1[i] + 1) * (y2[i] - d * (cy2 - 1));
                add(cx1, cy2, tt, s1, s2);
                /// colt st jos
                    tt = (x2[i] - d * (cx2 - 1)) * (d * cy1 - y1[i] + 1);
                add(cx2, cy1, tt, s1, s2);
                /// colt dr jos
                    tt = (x2[i] - d * (cx2 - 1)) * (y2[i] - d * (cy2 - 1));
                add(cx2, cy2, tt, s1, s2);
                /// marg sus si jos
                if(cy2 - cy1 - 1 >= 1)
                {
                    tt = (d * cx1 - x1[i] + 1) * d;
                    int np = cy2 - cy1 - 1;
                    int nri = np / 2, nrp = np / 2;
                    if(np % 2 == 1)
                        nri++;
                    add(cx1, cy1 + 1, tt * nri, s1, s2);
                    add(cx1, cy1 + 2, tt * nrp, s1, s2);
                    tt = (x2[i] - d * (cx2 - 1)) * d;
                    add(cx2, cy1 + 1, tt * nri, s1, s2);
                    add(cx2, cy1 + 2, tt * nrp, s1, s2);
                }
                /// marg st si dr
                if(cx2 - cx1 - 1 >= 1)
                {
                    tt = (d * cy1 - y1[i] + 1) * d;
                    int np = cx2 - cx1 - 1;
                    int nri = np / 2, nrp = np / 2;
                    if(np % 2 == 1)
                        nri++;
                    add(cx1 + 1, cy1, tt * nri, s1, s2);
                    add(cx1 + 2, cy1, tt * nrp, s1, s2);
                    tt = (y2[i] - d * (cy2 - 1)) * d;
                    add(cx1 + 1, cy2, tt * nri, s1, s2);
                    add(cx1 + 2, cy2, tt * nrp, s1, s2);
                }

                /// mijloc
                if((cx2 - cx1 - 1) * (cy2 - cy1 - 1) >= 1)
                {
                    int nrp = (cx2 - cx1 - 1) * (cy2 - cy1 - 1);
                    int d1 = nrp / 2, d2 = nrp / 2;
                    if(nrp % 2 == 1)
                        d1++;
                    add(cx1 + 1, cx2 + 1, d * d1, s1, s2);
                    add(cx1 + 1, cx2 + 2, d * d2, s1, s2);
                }
            }
        }

        int d1 = n * n, d2 = n * n;
        int nli = n / d / 2, nlp = n / d / 2;
        if((n / d) % 2 == 1) nli++;

        d2 -= (d * d * (nli * nli + nlp * nlp));
        d1 = n * n - d2;
        int ans = min(d1 - s1 + s2, d2 - s2 + s1);
        minn = min(minn, ans);
    }

    cout<<minn<<'\n';

    return 0;
}

Compilation message

chessboard.cpp: In function 'int main()':
chessboard.cpp:22:9: warning: unused variable 's1' [-Wunused-variable]
   22 |     int s1 = 0, s2 = 0;
      |         ^~
chessboard.cpp:22:17: warning: unused variable 's2' [-Wunused-variable]
   22 |     int s1 = 0, s2 = 0;
      |                 ^~

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 2260 KB Output is correct
2 Correct 19 ms 844 KB Output is correct
3 Correct 56 ms 1464 KB Output is correct
4 Correct 44 ms 1664 KB Output is correct
5 Correct 57 ms 1996 KB Output is correct
6 Correct 43 ms 1368 KB Output is correct
7 Correct 8 ms 468 KB Output is correct
8 Correct 37 ms 1408 KB Output is correct
9 Correct 95 ms 3108 KB Output is correct
10 Correct 51 ms 1768 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 29 ms 1184 KB Output is correct
17 Correct 71 ms 2888 KB Output is correct
18 Correct 92 ms 3400 KB Output is correct
19 Correct 138 ms 3020 KB Output is correct
20 Correct 141 ms 3396 KB Output is correct
21 Correct 71 ms 2764 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 41 ms 1624 KB Output is correct
24 Correct 86 ms 3100 KB Output is correct
25 Correct 9 ms 484 KB Output is correct
26 Correct 52 ms 1992 KB Output is correct
27 Correct 63 ms 2344 KB Output is correct
28 Correct 84 ms 3288 KB Output is correct
29 Correct 29 ms 1364 KB Output is correct
30 Correct 3 ms 352 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 2260 KB Output is correct
2 Correct 19 ms 844 KB Output is correct
3 Correct 56 ms 1464 KB Output is correct
4 Correct 44 ms 1664 KB Output is correct
5 Correct 57 ms 1996 KB Output is correct
6 Correct 43 ms 1368 KB Output is correct
7 Correct 8 ms 468 KB Output is correct
8 Correct 37 ms 1408 KB Output is correct
9 Correct 95 ms 3108 KB Output is correct
10 Correct 51 ms 1768 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 29 ms 1184 KB Output is correct
27 Correct 71 ms 2888 KB Output is correct
28 Correct 92 ms 3400 KB Output is correct
29 Correct 138 ms 3020 KB Output is correct
30 Correct 141 ms 3396 KB Output is correct
31 Correct 71 ms 2764 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 41 ms 1624 KB Output is correct
34 Correct 86 ms 3100 KB Output is correct
35 Correct 9 ms 484 KB Output is correct
36 Correct 52 ms 1992 KB Output is correct
37 Correct 63 ms 2344 KB Output is correct
38 Correct 84 ms 3288 KB Output is correct
39 Correct 29 ms 1364 KB Output is correct
40 Correct 3 ms 352 KB Output is correct
41 Correct 142 ms 2920 KB Output is correct
42 Correct 106 ms 3164 KB Output is correct
43 Correct 115 ms 2888 KB Output is correct
44 Correct 102 ms 3148 KB Output is correct
45 Correct 101 ms 3328 KB Output is correct
46 Correct 147 ms 3276 KB Output is correct
47 Correct 97 ms 2912 KB Output is correct
48 Correct 111 ms 3028 KB Output is correct
49 Correct 106 ms 2892 KB Output is correct
50 Correct 365 ms 3152 KB Output is correct
51 Correct 395 ms 3340 KB Output is correct
52 Correct 374 ms 3128 KB Output is correct
53 Correct 382 ms 3312 KB Output is correct
54 Correct 364 ms 3024 KB Output is correct
55 Correct 408 ms 3428 KB Output is correct
56 Correct 344 ms 3000 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 64 ms 2260 KB Output is correct
10 Correct 19 ms 844 KB Output is correct
11 Correct 56 ms 1464 KB Output is correct
12 Correct 44 ms 1664 KB Output is correct
13 Correct 57 ms 1996 KB Output is correct
14 Correct 43 ms 1368 KB Output is correct
15 Correct 8 ms 468 KB Output is correct
16 Correct 37 ms 1408 KB Output is correct
17 Correct 95 ms 3108 KB Output is correct
18 Correct 51 ms 1768 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 29 ms 1184 KB Output is correct
35 Correct 71 ms 2888 KB Output is correct
36 Correct 92 ms 3400 KB Output is correct
37 Correct 138 ms 3020 KB Output is correct
38 Correct 141 ms 3396 KB Output is correct
39 Correct 71 ms 2764 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 41 ms 1624 KB Output is correct
42 Correct 86 ms 3100 KB Output is correct
43 Correct 9 ms 484 KB Output is correct
44 Correct 52 ms 1992 KB Output is correct
45 Correct 63 ms 2344 KB Output is correct
46 Correct 84 ms 3288 KB Output is correct
47 Correct 29 ms 1364 KB Output is correct
48 Correct 3 ms 352 KB Output is correct
49 Correct 142 ms 2920 KB Output is correct
50 Correct 106 ms 3164 KB Output is correct
51 Correct 115 ms 2888 KB Output is correct
52 Correct 102 ms 3148 KB Output is correct
53 Correct 101 ms 3328 KB Output is correct
54 Correct 147 ms 3276 KB Output is correct
55 Correct 97 ms 2912 KB Output is correct
56 Correct 111 ms 3028 KB Output is correct
57 Correct 106 ms 2892 KB Output is correct
58 Correct 365 ms 3152 KB Output is correct
59 Correct 395 ms 3340 KB Output is correct
60 Correct 374 ms 3128 KB Output is correct
61 Correct 382 ms 3312 KB Output is correct
62 Correct 364 ms 3024 KB Output is correct
63 Correct 408 ms 3428 KB Output is correct
64 Correct 344 ms 3000 KB Output is correct
65 Correct 0 ms 212 KB Output is correct
66 Correct 1 ms 340 KB Output is correct
67 Correct 423 ms 3240 KB Output is correct
68 Correct 458 ms 5452 KB Output is correct
69 Correct 364 ms 4804 KB Output is correct
70 Correct 390 ms 5256 KB Output is correct
71 Correct 414 ms 5196 KB Output is correct
72 Correct 414 ms 5132 KB Output is correct
73 Correct 397 ms 5004 KB Output is correct
74 Correct 463 ms 5404 KB Output is correct
75 Incorrect 409 ms 5176 KB Output isn't correct
76 Halted 0 ms 0 KB -