CSES - Datatähti 2024 loppu

Submission details
Task:	Retkeily
Sender:	adex720
Submission time:	2024-01-20 16:04:08 +0200
Language:	C++ (C++11)
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	WRONG ANSWER	0
#2	WRONG ANSWER	0
#3	WRONG ANSWER	0
#4	WRONG ANSWER	0

Test results
test	verdict	time	group
#1	WRONG ANSWER	0.27 s	1, 2, 3, 4	details
#2	WRONG ANSWER	0.27 s	1, 2, 3, 4	details
#3	WRONG ANSWER	0.27 s	1, 2, 3, 4	details
#4	WRONG ANSWER	0.27 s	1, 2, 3, 4	details
#5	WRONG ANSWER	0.28 s	1, 2, 3, 4	details
#6	WRONG ANSWER	0.28 s	1, 2, 4	details
#7	WRONG ANSWER	0.28 s	1, 2, 4	details
#8	WRONG ANSWER	0.28 s	1, 2, 3, 4	details
#9	WRONG ANSWER	0.28 s	1, 2, 4	details
#10	WRONG ANSWER	0.28 s	1, 2, 3, 4	details
#11	WRONG ANSWER	0.28 s	1, 2, 4	details
#12	WRONG ANSWER	0.35 s	1, 2, 4	details
#13	WRONG ANSWER	0.39 s	1, 2, 4	details
#14	WRONG ANSWER	0.38 s	1, 2, 4	details
#15	WRONG ANSWER	0.38 s	1, 2, 4	details
#16	WRONG ANSWER	0.45 s	2, 4	details
#17	WRONG ANSWER	0.38 s	2, 4	details
#18	WRONG ANSWER	0.41 s	2, 4	details
#19	WRONG ANSWER	0.53 s	2, 3, 4	details
#20	WRONG ANSWER	0.45 s	2, 4	details
#21	WRONG ANSWER	0.51 s	2, 3, 4	details
#22	ACCEPTED	0.01 s	1, 3, 4	details
#23	ACCEPTED	0.01 s	1, 3, 4	details
#24	ACCEPTED	0.01 s	3, 4	details
#25	WRONG ANSWER	0.07 s	3, 4	details
#26	WRONG ANSWER	0.07 s	3, 4	details
#27	WRONG ANSWER	0.07 s	3, 4	details
#28	ACCEPTED	0.07 s	3, 4	details
#29	WRONG ANSWER	0.01 s	1, 4	details
#30	WRONG ANSWER	0.01 s	1, 4	details
#31	WRONG ANSWER	0.01 s	1, 4	details
#32	WRONG ANSWER	0.01 s	1, 4	details
#33	WRONG ANSWER	0.01 s	1, 4	details
#34	WRONG ANSWER	0.01 s	1, 4	details
#35	WRONG ANSWER	0.01 s	1, 4	details
#36	WRONG ANSWER	0.01 s	1, 4	details
#37	WRONG ANSWER	0.01 s	4	details
#38	WRONG ANSWER	0.07 s	4	details
#39	WRONG ANSWER	0.08 s	4	details
#40	WRONG ANSWER	0.07 s	4	details
#41	WRONG ANSWER	0.05 s	4	details

Code

#include <bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;

#define MP make_pair

void m1(int n, int m)
{
    pair<int, int> teltat[n];
    pair<int, int> paikat[m];

    int x, y;
    for (int i = 0; i < n; i++)
    {
        cin >> x >> y;
        teltat[i] = MP(x, y);
    }

    for (int i = 0; i < m; i++)
    {
        cin >> x >> y;
        paikat[i] = MP(x, y);
    }

    int suurin = 1;
    for (int i = 0; i < m; i++)
    {
        x = paikat[i].first;
        y = paikat[i].second;

        int pienin = INT_MAX;
        for (int j = 0; j < n; j++)
        {
            int etaisyys = abs(x - teltat[j].first) + abs(y - teltat[j].second);
            if (etaisyys < pienin)
            {
                pienin = etaisyys;
            }
        }

        if (pienin > suurin)
        {
            suurin = pienin;
        }
    }

    cout << suurin;
}

bool onTeltta(int x, int y, int n, pair<int, int> teltat[])
{
    int min = 0;
    int max = n - 1;

    while (true)
    {
        if (min >= max)
        {
            auto teltta = teltat[min];
            return teltta.first == x && teltta.second == y;
        }

        int keski = (min + max) >> 1;
        auto teltta = teltat[keski];

        if (teltta.first < x)
        {
            min = keski + 1;
            continue;
        }

        if (teltta.first > x)
        {
            max = keski - 1;
            continue;
        }

        if (teltta.second < y)
        {
            min = keski + 1;
            continue;
        }

        if (teltta.second > y)
        {
            max = keski - 1;
            continue;
        }

        return true;
    }
}

void m3(int n, int m, pair<int, int> teltat[], pair<int, int> paikat[])
{
    int x, y, x2, y2, y3;
    int suurin = 1;

    for (int i = 0; i < m; i++)
    {
        x = paikat[i].first;
        y = paikat[i].second;

        bool b = false;
        for (int d = 1; d <= 9; d++)
        {
            bool l = false;
            for (int m = -d; m < d; m++)
            {
                x2 = x + m;
                y2 = y + abs(d - abs(m));
                y3 = y - abs(d - abs(m));

                if (x2 < 0 || x2 > 1000)
                {
                    continue;
                }

                if (y2 <= 1000)
                {
                    if (onTeltta(x2, y2, n, teltat))
                    {
                        if (d > suurin)
                        {
                            suurin = d;
                        }
                        l = true;
                        break;
                    }
                }

                if (y3 >= 0)
                {
                    if (onTeltta(x2, y3, n, teltat))
                    {
                        if (d > suurin)
                        {
                            suurin = d;
                        }
                        l = true;
                        break;
                    }
                }
            }

            if (l)
            {
                b = true;
                break;
            }
        }

        if (!b)
        {
            cout << "10";
            return;
        }
    }

    cout << suurin;
}
void m2(int n, int m)
{

    pair<int, int> teltat[n];
    pair<int, int> paikat[m];

    int x, y;
    int isoin = 1;
    for (int i = 0; i < n; i++)
    {
        cin >> x >> y;
        x--;
        y--;
        teltat[i] = MP(x, y);
        if (isoin <= 1000)
        {
            isoin = max(x, y);
        }
    }

    for (int i = 0; i < m; i++)
    {
        cin >> x >> y;
        x--;
        y--;
        paikat[i] = MP(x, y);
        if (isoin <= 1000)
        {
            isoin = max(x, y);
        }
    }

    if (isoin > 1000)
    {
        sort(teltat, teltat + n); // ehkä
        sort(paikat, paikat + m); // ehkä
        m3(n, m, teltat, paikat);
        return;
    }

    int d[1000000];
    bool c[1000000];

    priority_queue<pair<int, pair<int, int>>> q;
    pair<int, int> teltta;

    for (int i = 0; i < n; i++)
    {
        teltta = teltat[i];
        x = teltta.first;
        y = teltta.second;

        d[x * 1000 + y] = 0;

        if (x > 0)
        {
            if (!c[(x - 1) * 1000 + y])
            {
                q.push(MP(-1, MP(x - 1, y)));
                c[(x - 1) * 1000 + y] = 1;
            }
        }
        if (x < 999)
        {
            if (!c[(x + 1) * 1000 + y])
            {
                q.push(MP(-1, MP(x + 1, y)));
                c[(x + 1) * 1000 + y] = 1;
            }
        }
        if (y > 0)
        {
            if (!c[x * 1000 + y - 1])
            {
                q.push(MP(-1, MP(x, y - 1)));
                c[x * 1000 + y - 1] = 1;
            }
        }
        if (y < 999)
        {
            if (!c[x * 1000 + y + 1])
            {
                q.push(MP(-1, MP(x, y + 1)));
                c[x * 1000 + y + 1] = 1;
            }
        }
    }

    int dist;
    while (!q.empty())
    {
        auto ruutu = q.top();
        q.pop();

        dist = -ruutu.first;
        x = ruutu.second.first;
        y = ruutu.second.second;

        cout << x << " " << y << "\n";

        d[x * 1000 + y] = dist;

        if (x > 0)
        {
            if (!c[(x - 1) * 1000 + y])
            {
                q.push(MP(-dist - 1, MP(x - 1, y)));
                c[(x - 1) * 1000 + y] = 1;
            }
        }
        if (x < 999)
        {
            if (!c[(x + 1) * 1000 + y])
            {
                q.push(MP(-dist - 1, MP(x + 1, y)));
                c[(x + 1) * 1000 + y] = 1;
            }
        }
        if (y > 0)
        {
            if (!c[x * 1000 + y - 1])
            {
                q.push(MP(-dist - 1, MP(x, y - 1)));
                c[x * 1000 + y - 1] = 1;
            }
        }
        if (y < 999)
        {
            if (!c[x * 1000 + y + 1])
            {
                q.push(MP(-dist - 1, MP(x, y + 1)));
                c[x * 1000 + y + 1] = 1;
            }
        }
    }

    int suurin = 1;
    int arvo;
    for (int i = 0; i < m; i++)
    {
        auto paikka = paikat[i];

        x = paikka.first;
        y = paikka.second;

        arvo = d[x * 1000 + y];
        if (arvo > suurin)
        {
            suurin = arvo;
        }
    }

    cout << suurin;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    /*if (n <= 1000 && m <= 1000)
    {
        m1(n, m);
        return 0;
    }*/

    m2(n, m);
}

Test details

Test 1

Group: 1, 2, 3, 4

Verdict: WRONG ANSWER

input
`1 1 6 6 8 9` view save

correct output
`5` view save

user output
`6 5 5 6 5 4 4 5 7 5 ...` Truncated

Test 2

Group: 1, 2, 3, 4

Verdict: WRONG ANSWER

input
`5 5 5 10 8 10 1 2 4 10 ...` view save

correct output
`4` view save

user output
`8 9 7 10 7 8 6 9 5 9 ...` Truncated

Test 3

Group: 1, 2, 3, 4

Verdict: WRONG ANSWER

input
`10 10 5 2 1 10 6 10 5 5 ...` view save

correct output
`5` view save

user output
`7 8 7 1 6 9 6 7 6 2 ...` Truncated

Test 4

Group: 1, 2, 3, 4

Verdict: WRONG ANSWER

input
`10 5 6 1 8 9 3 2 6 6 ...` view save

correct output
`3` view save

user output
`9 4 9 0 8 8 8 5 8 3 ...` Truncated

Test 5

Group: 1, 2, 3, 4

Verdict: WRONG ANSWER

input
`5 10 10 10 6 2 10 9 8 7 ...` view save

correct output
`7` view save

user output
`10 9 10 8 9 10 9 9 9 8 ...` Truncated

Test 6

Group: 1, 2, 4

Verdict: WRONG ANSWER

input
`1 1 55 68 28 42` view save

correct output
`53` view save

user output
`55 67 54 68 54 66 53 67 56 67 ...` Truncated

Test 7

Group: 1, 2, 4

Verdict: WRONG ANSWER

input
`100 100 52 56 58 96 3 99 18 1 ...` view save

correct output
`20` view save

user output
`100 60 99 61 99 59 98 60 98 45 ...` Truncated

Test 8

Group: 1, 2, 3, 4

Verdict: WRONG ANSWER

input
`1000 100 60 40 68 47 30 32 74 52 ...` view save

correct output
`5` view save

user output
`100 85 100 67 100 10 100 8 99 89 ...` Truncated

Test 9

Group: 1, 2, 4

Verdict: WRONG ANSWER

input
`100 1000 44 26 18 81 18 6 83 90 ...` view save

correct output
`20` view save

user output
`98 91 97 92 97 90 96 91 96 48 ...` Truncated

Test 10

Group: 1, 2, 3, 4

Verdict: WRONG ANSWER

input
`1000 1000 15 13 23 79 81 43 30 40 ...` view save

correct output
`7` view save

user output
`100 90 100 88 100 85 100 83 100 41 ...` Truncated

Test 11

Group: 1, 2, 4

Verdict: WRONG ANSWER

input
`1 1 948 495 227 149` view save

correct output
`1067` view save

user output
`948 494 947 495 947 493 946 494 949 494 ...` Truncated

Test 12

Group: 1, 2, 4

Verdict: WRONG ANSWER

input
`100 100 114 530 748 841 612 709 810 232 ...` view save

correct output
`203` view save

user output
`998 507 997 508 997 506 996 507 984 779 ...` Truncated

Test 13

Group: 1, 2, 4

Verdict: WRONG ANSWER

input
`1000 100 225 82 265 691 978 367 993 396 ...` view save

correct output
`50` view save

user output
`998 113 997 114 997 112 996 113 995 299 ...` Truncated

Test 14

Group: 1, 2, 4

Verdict: WRONG ANSWER

input
`100 1000 848 668 189 716 451 80 626 973 ...` view save

correct output
`192` view save

user output
`983 642 982 643 982 641 981 642 978 108 ...` Truncated

Test 15

Group: 1, 2, 4

Verdict: WRONG ANSWER

input
`1000 1000 931 656 382 809 666 609 1000 923 ...` view save

correct output
`66` view save

user output
`999 929 999 923 999 921 999 530 999 528 ...` Truncated

Test 16

Group: 2, 4

Verdict: WRONG ANSWER

input
`10000 1000 961 158 561 313 991 125 821 964 ...` view save

correct output
`18` view save

user output
`999 999 999 920 999 919 999 917 999 876 ...` Truncated

Test 17

Group: 2, 4

Verdict: WRONG ANSWER

input
`1000 10000 428 1000 485 958 46 915 582 127 ...` view save

correct output
`67` view save

user output
`999 816 999 814 999 772 999 268 999 266 ...` Truncated

Test 18

Group: 2, 4

Verdict: WRONG ANSWER

input
`10000 10000 503 849 367 829 448 926 362 512 ...` view save

correct output
`22` view save

user output
`999 877 999 875 999 831 999 830 999 829 ...` Truncated

Test 19

Group: 2, 3, 4

Verdict: WRONG ANSWER

input
`100000 10000 111 705 808 24 69 858 961 122 ...` view save

correct output
`7` view save

user output
`999 998 999 996 999 994 999 989 999 980 ...` Truncated

Test 20

Group: 2, 4

Verdict: WRONG ANSWER

input
`10000 100000 844 874 339 315 819 918 627 936 ...` view save

correct output
`27` view save

user output
`999 983 999 942 999 933 999 931 999 912 ...` Truncated

Test 21

Group: 2, 3, 4

Verdict: WRONG ANSWER

input
`100000 100000 100 468 303 899 784 458 505 54 ...` view save

correct output
`8` view save

user output
`999 997 999 996 999 995 999 992 999 990 ...` Truncated

Test 22

Group: 1, 3, 4

Verdict: ACCEPTED

input
`10 10 451219 220496 369161 161920 241139 700531 811276 993633 ...` view save

correct output
`10` view save

user output
`10` view save

Test 23

Group: 1, 3, 4

Verdict: ACCEPTED

input
`1000 1000 337358 113599 674585 852084 717817 983395 895431 391144 ...` view save

correct output
`10` view save

user output
`10` view save

Test 24

Group: 3, 4

Verdict: ACCEPTED

input
`10000 10000 636432 664736 341727 37864 469264 360610 545785 879043 ...` view save

correct output
`10` view save

user output
`10` view save

Test 25

Group: 3, 4

Verdict: WRONG ANSWER

input
`100000 100000 750315 55215 550921 465416 435380 742666 288479 495099 ...` view save

correct output
`7` view save

user output
`10` view save

Test 26

Group: 3, 4

Verdict: WRONG ANSWER

input
`100000 100000 416825 677767 347155 162523 602643 936386 181956 517732 ...` view save

correct output
`8` view save

user output
`10` view save

Test 27

Group: 3, 4

Verdict: WRONG ANSWER

input
`100000 100000 155202 457283 421100 55104 604625 136495 841749 569346 ...` view save

correct output
`9` view save

user output
`10` view save

Test 28

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 290146 808578 489810 268578 956361 635214 939844 534435 ...` view save

correct output
`10` view save

user output
`10` view save

Test 29

Group: 1, 4

Verdict: WRONG ANSWER

input
`10 10 668880 791821 226050 188133 859493 736633 290460 838926 ...` view save

correct output
`342068` view save

user output
`10` view save

Test 30

Group: 1, 4

Verdict: WRONG ANSWER

input
`100 100 729367 697755 338457 742774 535371 701216 93743 555995 ...` view save

correct output
`285526` view save

user output
`10` view save

Test 31

Group: 1, 4

Verdict: WRONG ANSWER

input
`100 1000 50870 539657 476809 462765 311713 355546 901838 829393 ...` view save

correct output
`255789` view save

user output
`10` view save

Test 32

Group: 1, 4

Verdict: WRONG ANSWER

input
`1000 100 182415 659794 581623 510256 594984 525993 367726 938015 ...` view save

correct output
`50501` view save

user output
`10` view save

Test 33

Group: 1, 4

Verdict: WRONG ANSWER

input
`1000 1000 668976 422918 350791 933024 893307 88057 278098 13847 ...` view save

correct output
`57897` view save

user output
`10` view save

Test 34

Group: 1, 4

Verdict: WRONG ANSWER

input
`1000 1000 701742 116334 278337 368995 187245 133297 273083 369187 ...` view save

correct output
`60537` view save

user output
`10` view save

Test 35

Group: 1, 4

Verdict: WRONG ANSWER

input
`10 10 693836 74759 61731 520849 666762 45364 559335 979511 ...` view save

correct output
`417182` view save

user output
`10` view save

Test 36

Group: 1, 4

Verdict: WRONG ANSWER

input
`1000 1000 207572 43521 513003 683552 58800 253576 16541 558695 ...` view save

correct output
`69609` view save

user output
`10` view save

Test 37

Group: 4

Verdict: WRONG ANSWER

input
`10000 10000 89066 605574 504488 66068 959128 348414 68004 849599 ...` view save

correct output
`22936` view save

user output
`10` view save

Test 38

Group: 4

Verdict: WRONG ANSWER

input
`100000 100000 20824 214259 463783 904059 603615 769692 789080 399093 ...` view save

correct output
`8070` view save

user output
`10` view save

Test 39

Group: 4

Verdict: WRONG ANSWER

input
`100000 100000 811424 464350 336948 946495 204883 914446 171888 431769 ...` view save

correct output
`8240` view save

user output
`10` view save

Test 40

Group: 4

Verdict: WRONG ANSWER

input
`100000 100000 850810 902354 292608 63461 223139 188900 197760 995048 ...` view save

correct output
`7769` view save

user output
`10` view save

Test 41

Group: 4

Verdict: WRONG ANSWER

input
`100000 100000 1 1 1 2 1 3 1 4 ...` view save

correct output
`1899999` view save

user output
`10` view save

Datatähti 2024 loppu

Retkeily

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Tasks

Submissions (adex720)