CSES - Datatähti 2024 alku - Results
Submission details
Task:Käännöt
Sender:adex720
Submission time:2023-11-09 19:44:12 +0200
Language:C++20
Status:READY
Result:32
Feedback
groupverdictscore
#1ACCEPTED13
#2ACCEPTED19
#30
#40
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1details
#2ACCEPTED0.00 s1details
#3ACCEPTED0.00 s1details
#4ACCEPTED0.00 s1details
#5ACCEPTED0.00 s1details
#6ACCEPTED0.00 s2details
#7ACCEPTED0.00 s2details
#8ACCEPTED0.00 s2details
#9ACCEPTED0.00 s2details
#10ACCEPTED0.00 s2details
#11ACCEPTED0.01 s2details
#12ACCEPTED0.01 s2details
#13ACCEPTED0.01 s2details
#14ACCEPTED0.01 s2details
#15ACCEPTED0.00 s2details
#16ACCEPTED0.01 s2details
#17ACCEPTED0.00 s3details
#18ACCEPTED0.00 s3details
#190.00 s3details
#200.00 s3details
#210.00 s3details
#220.00 s3details
#230.00 s3details
#240.01 s3details
#25ACCEPTED0.01 s3details
#260.00 s4details
#270.00 s4details
#280.00 s4details
#290.00 s4details
#300.00 s4details
#310.00 s4details
#320.00 s4details
#330.00 s4details
#340.00 s4details

Code

#include <bits/stdc++.h>
using namespace std;

void k2(int n, int luvut[])
{
    int maara = 0;
    vector<int> siirrot = {};

    int eka;
    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = 0; j < i; j++)
        {
            eka = luvut[j];
            if (eka > luvut[j + 1])
            {
                maara++;
                siirrot.push_back(j);
                luvut[j] = luvut[j + 1];
                luvut[j + 1] = eka;
            }
        }
    }

    cout << "YES\n"
         << maara << "\n";
    for (int siirto : siirrot)
    {
        cout << siirto + 1 << " ";
    }
}

void k3(int n, int luvut[])
{
    int maara = 0;
    vector<int> siirrot = {};

    int parittomia = (n + 1) / 2;
    int parillisia = n / 2;
    int parittomat[parittomia];
    int parilliset[parillisia];

    // lisätään omiin listoihin
    for (int i = 0; i < parillisia; i++)
    {
        parittomat[i] = luvut[2 * i];
        parilliset[i] = luvut[2 * i + 1];
    }

    if (parillisia != parittomia)
    {
        parittomat[parillisia] = luvut[n - 1];
    }

    // järjestetään listat
    int eka;
    for (int i = parittomia - 1; i >= 0; i--)
    {
        for (int j = 0; j < i; j++)
        {
            eka = parittomat[j];
            if (eka > parittomat[j + 1])
            {
                maara++;
                siirrot.push_back(2 * j);
                parittomat[j] = parittomat[j + 1];
                parittomat[j + 1] = eka;
            }
        }
    }

    for (int i = parillisia - 1; i >= 0; i--)
    {
        for (int j = 0; j < i; j++)
        {
            eka = parilliset[j];
            if (eka > parilliset[j + 1])
            {
                maara++;
                siirrot.push_back(2 * j + 1);
                parilliset[j] = parilliset[j + 1];
                parilliset[j + 1] = eka;
            }
        }
    }

    // tarkistetaan onko kaikki suuruusjärjestyksessä.
    if (parittomat[0] > parilliset[0])
    {
        cout << "NO";
        return;
    }

    for (int i = 1; i < parillisia; i++)
    {
        if (parittomat[i] > parilliset[i] || parilliset[i - 1] > parittomat[i])
        {
            cout << "NO";
            return;
        }
    }

    if (parillisia != parittomia)
    {
        if (parilliset[parillisia - 1] > parittomat[parillisia])
        {
            cout << "NO";
            return;
        }
    }

    cout << "YES\n"
         << maara << "\n";
    for (int siirto : siirrot)
    {
        cout << siirto + 1 << " ";
    }
}

void k4n5(int luvut[])
{
    vector<int> siirrot = {};
    int temp1, temp2;

    int siirto = 0;
    for (int i = 0; i < 11; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            if (luvut[j] != j + 1)
                break;;

            if (j != 3)
                continue;

            cout << "YES\n"
                 << siirrot.size() << "\n";
            for (int siirto1 : siirrot)
            {
                cout << (siirto1 + 1) << " ";
            }

            return;
        }

        siirrot.push_back(siirto);

        temp1 = luvut[3 + siirto];
        temp2 = luvut[2 + siirto];
        luvut[3 + siirto] = luvut[0 + siirto];
        luvut[2 + siirto] = luvut[1 + siirto];
        luvut[0 + siirto] = temp1;
        luvut[1 + siirto] = temp2;

        siirto ^= 1;
    }

    cout << "NO";
}

void k4n6(int luvut[])
{
    vector<int> siirrot = {};
    int temp1, temp2;

    if (luvut[0] == 6)
    {
        siirrot.push_back(0);

        temp1 = luvut[3];
        temp2 = luvut[2];
        luvut[3] = luvut[0];
        luvut[2] = luvut[1];
        luvut[0] = temp1;
        luvut[1] = temp2;
    }

    if (luvut[3] == 6 || luvut[4] == 6)
    {
        siirrot.push_back(1);

        temp1 = luvut[4];
        temp2 = luvut[3];
        luvut[4] = luvut[1];
        luvut[3] = luvut[2];
        luvut[1] = temp1;
        luvut[2] = temp2;
    }

    if (luvut[1] == 6)
    {
        siirrot.push_back(0);

        temp1 = luvut[3];
        temp2 = luvut[2];
        luvut[3] = luvut[0];
        luvut[2] = luvut[1];
        luvut[0] = temp1;
        luvut[1] = temp2;
    }

    if (luvut[2] == 6)
    {
        siirrot.push_back(2);

        temp1 = luvut[5];
        temp2 = luvut[4];
        luvut[5] = luvut[2];
        luvut[4] = luvut[3];
        luvut[2] = temp1;
        luvut[3] = temp2;
    }

    if (luvut[0] == 5)
    {
        siirrot.push_back(0);

        temp1 = luvut[3];
        temp2 = luvut[2];
        luvut[3] = luvut[0];
        luvut[2] = luvut[1];
        luvut[0] = temp1;
        luvut[1] = temp2;
    }

    if (luvut[3] == 5)
    {
        siirrot.push_back(1);

        temp1 = luvut[4];
        temp2 = luvut[3];
        luvut[4] = luvut[1];
        luvut[3] = luvut[2];
        luvut[1] = temp1;
        luvut[2] = temp2;
    }

    if (luvut[2] == 5)
    {
        siirrot.push_back(0);

        temp1 = luvut[3];
        temp2 = luvut[2];
        luvut[3] = luvut[0];
        luvut[2] = luvut[1];
        luvut[0] = temp1;
        luvut[1] = temp2;
    }

    if (luvut[1] == 5)
    {
        siirrot.push_back(1);

        temp1 = luvut[4];
        temp2 = luvut[3];
        luvut[4] = luvut[1];
        luvut[3] = luvut[2];
        luvut[1] = temp1;
        luvut[2] = temp2;
    }

    if (luvut[2] == 4 || luvut[0] == 4)
    {
        siirrot.push_back(0);

        temp1 = luvut[3];
        temp2 = luvut[4];
        luvut[3] = luvut[2];
        luvut[2] = luvut[1];
        luvut[0] = temp1;
        luvut[1] = temp2;
    }

    if (luvut[1] == 4)
    {
        siirrot.push_back(2);
        siirrot.push_back(1);
        siirrot.push_back(0);
        siirrot.push_back(2);
        siirrot.push_back(0);
        siirrot.push_back(1);
        siirrot.push_back(2);
        siirrot.push_back(0);

        temp1 = luvut[3];
        temp2 = luvut[2];
        luvut[3] = luvut[1];
        luvut[2] = luvut[0];
        luvut[1] = temp1;
        luvut[0] = temp2;
    }

    if (luvut[0] != 1)
    {
        cout << "NO";
        return;
    }

    cout << "YES\n"
         << siirrot.size() << "\n";
    for (int siirto : siirrot)
    {
        cout << (siirto + 1) << " ";
    }
}

void k4n7(int luvut[])
{
}

void k4(int n, int luvut[])
{
    if (n <= 7)
    {
        if (n == 5)
        {
            k4n5(luvut);
            return;
        }
        if (n == 6)
        {
            k4n6(luvut);
            return;
        }
        k4n7(luvut);
        return;
    }

    vector<int> siirrot = {};

    int temp1, temp2;

    int haluttuIndex = n;
    int haluttuMod3 = n % 3;
    int nykyinenIndex;
    for (int nykyinen = n; nykyinen > 6; nykyinen--)
    {
        haluttuIndex--;
        haluttuMod3--;
        if (haluttuMod3 < 0)
        {
            haluttuMod3 = 2;
        }

        for (int i = 0; i < nykyinen; i++)
        {
            if (luvut[i] == nykyinen)
            {
                nykyinenIndex = i;
                break;
            }
        }

        if (nykyinenIndex == haluttuIndex)
        {
            continue;
        }

        if (nykyinenIndex >= nykyinen - 3)
        {
            siirrot.push_back(nykyinenIndex - 3);

            temp1 = luvut[nykyinenIndex - 3];
            temp2 = luvut[nykyinenIndex - 2];
            luvut[nykyinenIndex - 3] = luvut[nykyinenIndex];
            luvut[nykyinenIndex - 2] = luvut[nykyinenIndex - 1];
            luvut[nykyinenIndex] = temp1;
            luvut[nykyinenIndex - 1] = temp2;

            nykyinenIndex -= 3;
        }

        if (nykyinenIndex == 0)
        {
            siirrot.push_back(nykyinenIndex);

            temp1 = luvut[nykyinenIndex + 3];
            temp2 = luvut[nykyinenIndex + 2];
            luvut[nykyinenIndex + 3] = luvut[nykyinenIndex];
            luvut[nykyinenIndex + 2] = luvut[nykyinenIndex + 1];
            luvut[nykyinenIndex] = temp1;
            luvut[nykyinenIndex + 1] = temp2;

            nykyinenIndex += 3;
        }

        int siirto = (haluttuIndex - nykyinenIndex) % 3;

        for (int j = 0; j < siirto; j++)
        {
            siirrot.push_back(nykyinenIndex - 1);

            temp1 = luvut[nykyinenIndex + 2];
            temp2 = luvut[nykyinenIndex + 1];
            luvut[nykyinenIndex + 2] = luvut[nykyinenIndex - 1];
            luvut[nykyinenIndex + 1] = luvut[nykyinenIndex];
            luvut[nykyinenIndex - 1] = temp1;
            luvut[nykyinenIndex] = temp2;

            nykyinenIndex++;
        }

        while (nykyinenIndex != haluttuIndex)
        {
            siirrot.push_back(nykyinenIndex);

            temp1 = luvut[nykyinenIndex + 3];
            temp2 = luvut[nykyinenIndex + 2];
            luvut[nykyinenIndex + 3] = luvut[nykyinenIndex];
            luvut[nykyinenIndex + 2] = luvut[nykyinenIndex + 1];
            luvut[nykyinenIndex] = temp1;
            luvut[nykyinenIndex + 1] = temp2;

            nykyinenIndex += 3;
        }
    }

    // jarjesta 6.
    if (n > 5)
    {
        for (int i = 0; i < 6; i++)
        {
            if (luvut[i] == 6)
            {
                nykyinenIndex = i;
                break;
            }
        }

        if (nykyinenIndex == 0)
        {
            siirrot.push_back(0);

            temp1 = luvut[3];
            temp2 = luvut[2];
            luvut[3] = luvut[0];
            luvut[2] = luvut[1];
            luvut[0] = temp1;
            luvut[1] = temp2;

            nykyinenIndex = 3;
        }

        if (nykyinenIndex == 3 || nykyinenIndex == 4)
        {
            siirrot.push_back(1);

            temp1 = luvut[4];
            temp2 = luvut[3];
            luvut[4] = luvut[1];
            luvut[3] = luvut[2];
            luvut[1] = temp1;
            luvut[2] = temp2;

            nykyinenIndex = 5 - nykyinenIndex;
        }

        if (nykyinenIndex == 1)
        {
            siirrot.push_back(0);

            temp1 = luvut[3];
            temp2 = luvut[2];
            luvut[3] = luvut[0];
            luvut[2] = luvut[1];
            luvut[0] = temp1;
            luvut[1] = temp2;

            nykyinenIndex = 2;
        }

        if (nykyinenIndex == 2)
        {
            siirrot.push_back(2);

            temp1 = luvut[5];
            temp2 = luvut[4];
            luvut[5] = luvut[2];
            luvut[4] = luvut[3];
            luvut[2] = temp1;
            luvut[3] = temp2;
        }
    }

    // järjestä 5
    for (int i = 0; i < 5; i++)
    {
        if (luvut[i] == 5)
        {
            nykyinenIndex = i;
            break;
        }
    }

    if (nykyinenIndex == 0)
    {
        siirrot.push_back(0);

        temp1 = luvut[3];
        temp2 = luvut[2];
        luvut[3] = luvut[0];
        luvut[2] = luvut[1];
        luvut[0] = temp1;
        luvut[1] = temp2;

        nykyinenIndex = 3;
    }

    if (nykyinenIndex == 3)
    {
        siirrot.push_back(1);

        temp1 = luvut[4];
        temp2 = luvut[3];
        luvut[4] = luvut[1];
        luvut[3] = luvut[2];
        luvut[1] = temp1;
        luvut[2] = temp2;

        nykyinenIndex = 2;
    }

    if (nykyinenIndex == 2)
    {
        siirrot.push_back(0);

        temp1 = luvut[3];
        temp2 = luvut[2];
        luvut[3] = luvut[0];
        luvut[2] = luvut[1];
        luvut[0] = temp1;
        luvut[1] = temp2;

        nykyinenIndex = 1;
    }

    if (nykyinenIndex == 1)
    {
        siirrot.push_back(1);

        temp1 = luvut[4];
        temp2 = luvut[3];
        luvut[4] = luvut[1];
        luvut[3] = luvut[2];
        luvut[1] = temp1;
        luvut[2] = temp2;
    }

    // siirrä 4. 4.
    for (int i = 0; i < 5; i++)
    {
        if (luvut[i] == 5)
        {
            nykyinenIndex = i;
            break;
        }
    }

    if (nykyinenIndex == 0)
    {
        siirrot.push_back(0);

        temp1 = luvut[3];
        temp2 = luvut[2];
        luvut[3] = luvut[0];
        luvut[2] = luvut[1];
        luvut[0] = temp1;
        luvut[1] = temp2;

        nykyinenIndex = 3;
    }
    if (nykyinenIndex == 2)
    {
        siirrot.push_back(1);

        temp1 = luvut[4];
        temp2 = luvut[3];
        luvut[4] = luvut[1];
        luvut[3] = luvut[2];
        luvut[1] = temp1;
        luvut[2] = temp2;

        nykyinenIndex = 1;
    }

    if (nykyinenIndex == 1)
    {
        siirrot.push_back(2);
        siirrot.push_back(1);
        siirrot.push_back(0);
        siirrot.push_back(2);
        siirrot.push_back(0);
        siirrot.push_back(1);
        siirrot.push_back(2);
        siirrot.push_back(0);

        temp1 = luvut[3];
        temp2 = luvut[2];
        luvut[3] = luvut[1];
        luvut[2] = luvut[0];
        luvut[1] = temp1;
        luvut[0] = temp2;
    }

    if ((luvut[1] - luvut[0] + 3) % 3 != 1)
    {
        cout << "NO";
        return;
    }

    for (int i = luvut[0]; i > 1; i--)
    {
        siirrot.push_back(1);
        siirrot.push_back(4);
        siirrot.push_back(3);
        siirrot.push_back(1);
        siirrot.push_back(0);
        siirrot.push_back(3);
        siirrot.push_back(1);
        siirrot.push_back(0);
        siirrot.push_back(4);
        siirrot.push_back(1);
        siirrot.push_back(2);
        siirrot.push_back(4);
        siirrot.push_back(0);
        siirrot.push_back(3);
    }

    cout << "YES\n"
         << siirrot.size() << "\n";
    for (int siirto : siirrot)
    {
        cout << (siirto + 1) << " ";
    }
}

void k5(int n, int luvut[])
{
}

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

    int n, k;
    cin >> n >> k;

    int luvut[n];

    for (int i = 0; i < n; i++)
    {
        cin >> luvut[i];
    }

    if (k == 2)
    {
        k2(n, luvut);
    }
    else if (k == 3)
    {
        k3(n, luvut);
    }
    else if (k == 4)
    {
        k4(n, luvut);
    }
    else if (k == 5)
    {
        k5(n, luvut);
    }
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
5 2
1 2 3 4 5

correct output
YES
0

user output
YES
0

Test 2

Group: 1

Verdict: ACCEPTED

input
5 2
2 1 3 4 5

correct output
YES
1
1

user output
YES
1

Test 3

Group: 1

Verdict: ACCEPTED

input
20 2
6 20 18 2 16 13 19 17 8 14 11 ...

correct output
YES
366
2 3 4 5 6 7 8 9 10 11 12 13 14...

user output
YES
132
2 3 4 5 6 7 8 9 10 11 12 13 14...
Truncated

Test 4

Group: 1

Verdict: ACCEPTED

input
100 2
100 92 62 88 12 7 43 31 19 72 ...

correct output
YES
2876
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
YES
2438
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
Truncated

Test 5

Group: 1

Verdict: ACCEPTED

input
100 2
100 99 98 97 96 95 94 93 92 91...

correct output
YES
5248
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
YES
4950
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
Truncated

Test 6

Group: 2

Verdict: ACCEPTED

input
5 3
1 2 3 4 5

correct output
YES
0

user output
YES
0

Test 7

Group: 2

Verdict: ACCEPTED

input
5 3
3 5 4 1 2

correct output
NO

user output
NO

Test 8

Group: 2

Verdict: ACCEPTED

input
5 3
5 2 1 4 3

correct output
YES
8
1 2 1 3 1 2 3 1

user output
YES
2
1 3 

Test 9

Group: 2

Verdict: ACCEPTED

input
20 3
19 14 1 18 3 4 11 20 13 6 17 8...

correct output
YES
52
8 10 12 14 16 18 1 3 5 7 9 11 ...

user output
YES
42
1 3 5 7 9 11 13 15 17 9 11 13 ...
Truncated

Test 10

Group: 2

Verdict: ACCEPTED

input
20 3
9 6 13 18 5 10 3 2 7 20 1 4 19...

correct output
YES
50
10 12 14 16 18 13 15 17 4 6 8 ...

user output
YES
34
3 5 7 9 13 15 17 1 3 5 7 11 1 ...

Test 11

Group: 2

Verdict: ACCEPTED

input
500 3
53 52 21 76 25 142 5 4 83 176 ...

correct output
YES
15194
334 336 338 340 342 344 346 34...

user output
YES
15174
1 3 5 11 13 15 17 19 25 27 29 ...
Truncated

Test 12

Group: 2

Verdict: ACCEPTED

input
500 3
51 44 147 172 1 28 27 82 233 1...

correct output
YES
15565
366 368 370 372 374 376 378 38...

user output
YES
15543
3 5 11 13 15 17 19 21 23 27 29...
Truncated

Test 13

Group: 2

Verdict: ACCEPTED

input
500 3
75 46 179 62 221 14 67 154 89 ...

correct output
YES
15920
454 456 458 460 462 464 466 46...

user output
YES
15902
5 7 9 11 13 15 19 21 23 25 27 ...
Truncated

Test 14

Group: 2

Verdict: ACCEPTED

input
500 3
161 54 285 12 71 142 111 94 97...

correct output
YES
15931
408 410 412 414 416 418 420 42...

user output
YES
15907
3 5 7 9 11 13 15 17 19 21 23 2...
Truncated

Test 15

Group: 2

Verdict: ACCEPTED

input
500 3
122 260 455 113 315 276 433 43...

correct output
NO

user output
NO

Test 16

Group: 2

Verdict: ACCEPTED

input
500 3
499 500 497 498 495 496 493 49...

correct output
YES
62264
2 4 6 8 10 12 14 16 18 20 22 2...

user output
YES
62250
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 17

Group: 3

Verdict: ACCEPTED

input
5 4
1 2 3 4 5

correct output
YES
0

user output
YES
0

Test 18

Group: 3

Verdict: ACCEPTED

input
5 4
5 1 2 3 4

correct output
YES
4
1 2 1 2

user output
YES
4
1 2 1 2 

Test 19

Group: 3

Verdict:

input
500 4
58 14 107 124 4 113 24 290 56 ...

correct output
YES
15698
389 392 395 398 401 404 407 41...

user output
NO

Test 20

Group: 3

Verdict:

input
500 4
113 187 278 242 23 67 48 298 3...

correct output
YES
15004
480 481 480 482 485 488 491 49...

user output
NO

Test 21

Group: 3

Verdict:

input
500 4
5 233 199 35 213 354 11 134 30...

correct output
YES
16770
458 461 464 467 470 473 476 47...

user output
NO

Test 22

Group: 3

Verdict:

input
500 4
169 47 21 137 57 138 360 147 4...

correct output
YES
15889
497 371 372 371 373 376 379 38...

user output
NO

Test 23

Group: 3

Verdict:

input
500 4
493 409 291 313 156 443 496 40...

correct output
YES
22886
480 481 480 482 485 488 491 49...

user output
NO

Test 24

Group: 3

Verdict:

input
500 4
137 99 100 226 326 298 140 340...

correct output
NO

user output
YES
21694
467 468 470 473 476 479 482 48...
Truncated

Test 25

Group: 3

Verdict: ACCEPTED

input
500 4
500 499 498 497 496 495 494 49...

correct output
YES
41458
1 2 1 2 5 8 11 14 17 20 23 26 ...

user output
YES
41580
1 3 5 8 11 14 17 20 23 26 29 3...
Truncated

Test 26

Group: 4

Verdict:

input
5 5
1 2 3 4 5

correct output
YES
0

user output
(empty)

Test 27

Group: 4

Verdict:

input
5 5
5 4 3 2 1

correct output
YES
1
1

user output
(empty)

Test 28

Group: 4

Verdict:

input
500 5
145 26 285 154 147 314 141 40 ...

correct output
YES
13786
216 220 224 228 232 236 240 24...

user output
(empty)

Test 29

Group: 4

Verdict:

input
500 5
137 22 399 292 249 6 51 224 42...

correct output
YES
13465
456 460 464 468 472 476 480 48...

user output
(empty)

Test 30

Group: 4

Verdict:

input
500 5
153 52 85 100 329 60 433 468 4...

correct output
YES
13642
377 378 377 380 384 388 392 39...

user output
(empty)

Test 31

Group: 4

Verdict:

input
500 5
267 326 95 108 189 32 291 366 ...

correct output
YES
14639
213 214 213 216 220 224 228 23...

user output
(empty)

Test 32

Group: 4

Verdict:

input
500 5
15 450 272 80 321 101 247 438 ...

correct output
NO

user output
(empty)

Test 33

Group: 4

Verdict:

input
499 5
497 498 499 496 495 494 493 49...

correct output
YES
30886
3 7 11 15 19 23 27 31 35 39 43...

user output
(empty)

Test 34

Group: 4

Verdict:

input
500 5
499 500 497 498 495 496 493 49...

correct output
YES
30919
1 4 8 12 16 20 24 28 32 36 40 ...

user output
(empty)