Submission #160310

#	Time	Username	Problem	Language	Result	Execution time	Memory
160310		model_code	Cat (info1cup19_cat)	C++17	100 / 100	781 ms	15340 KiB

cat

/*
Costin
Solutie de 100, O (N), nu foarte constant-friendly, dar implementata elegant
*/
#include<bits/stdc++.h>

using namespace std;

const int maxM = 200000;
int M, N, init[maxM + 10], a[(maxM / 2) + 10], b[(maxM / 2) + 10], c[(maxM / 2) + 10], p[(maxM / 2) + 10];
bool ap[maxM + 10];
vector < vector < int > > cycles;
vector < int > oddCycleRepresentatives;
vector < pair < int, int > > moves;

void makeSure (int x, int l, int r)
{
    assert (l <= x && x <= r);
}

void read ()
{
    scanf ("%d", &M), N = M >> 1;
    makeSure (M, 1, maxM);
    for (int i=1; i<=M; i++)
        ap[i] = 0;
    for (int i=1; i<=M; i++)
    {
        scanf ("%d", &init[i]);
        makeSure (init[i], 1, M);
        assert (!ap[init[i]]);
        ap[init[i]] = 1;
    }
    assert (M % 2 == 0);
}

void convertToNicerForm (bool &failed)
{
    for (int i=1; i<=N; i++)
        a[i] = init[i], b[i] = init[M + 1 - i];
    bool needJump = 0;
    for (int i=1; i<=N; i++)
        if (a[i] + b[i] != M + 1) failed = 1;
        else c[i] = (a[i] > N), p[i] = min (a[i], b[i]), needJump ^= c[i];
    if (needJump) failed = 1;
}

void findCycles ()
{
    cycles.clear ();
    oddCycleRepresentatives.clear ();
    for (int i=1; i<=N; i++)
        ap[i] = 0;
    for (int i=1; i<=N; i++)
        if (ap[i] == 0)
        {
            int j = p[i], overallParity = 0;
            ap[i] = 1, overallParity ^= c[i];
            vector < int > currCycle = {i};
            while (j != i)
                currCycle.push_back (j),
                overallParity ^= c[j],
                ap[j] = 1, j = p[j];
            cycles.push_back (currCycle);
            if (overallParity)
                oddCycleRepresentatives.push_back (i);
        }
}

void performSwap (int x, int y, bool xorValue)
{
    swap (p[x], p[y]);
    swap (c[x], c[y]);
    c[x] ^= xorValue, c[y] ^= xorValue;
    if (!xorValue) moves.push_back ({x, y});
    else moves.push_back ({x, M + 1 - y});
}

void mergeCycles ()
{
    assert (oddCycleRepresentatives.size () % 2 == 0);
    for (int i=1; i<oddCycleRepresentatives.size (); i+=2)
        performSwap (oddCycleRepresentatives[i - 1], oddCycleRepresentatives[i], 0);
}

void solve (int i, int j, vector < int > &cycle)
{
    if (i == j)
        return ;
    int L = cycle.size (), k = (i + 1) % L;
    while (1)
    {
        performSwap (cycle[i], cycle[k], 0);
        if (k == j) break;
        if (++k == L)
            k = 0;
    }
}

void fixCycle (vector < int > &currCycle)
{
    int L = currCycle.size ();
    vector < int > needXor;
    for (int i=0; i<L; i++)
    {
        ap[i] = 0;
        if (c[currCycle[i]])
            needXor.push_back (i);
    }
    assert (needXor.size () % 2 == 0);
    if (needXor.empty ())
    {
        solve (0, L - 1, currCycle);
        return ;
    }
    for (int currPos=1; currPos<needXor.size (); currPos+=2)
    {
        int i = needXor[currPos - 1], j = needXor[currPos];
        performSwap (currCycle[i], currCycle[j], 1);
        for (int k=i + 1; k<=j; k++)
            ap[k] = 1;
        solve (i + 1, j, currCycle);
    }
    vector < int > leftOver;
    for (int k=0; k<L; k++)
        if (!ap[k])
            leftOver.push_back (currCycle[k]);
    solve (0, leftOver.size () - 1, leftOver);
}

void print ()
{
    printf ("%d %d\n", moves.size (), moves.size ());
    for (auto it : moves)
        printf ("%d %d\n", it.first, it.second);
}

void check ()
{
    for (int i=1; i<=N; i++)
        assert (p[i] == i), assert (c[i] == 0);
    for (auto it : moves)
    {
        int x = it.first, y = it.second;
        swap (init[x], init[y]);
        swap (init[M + 1 - x], init[M + 1 - y]);
    }
    for (int i=1; i<=M; i++)
        assert (init[i] == i);
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

int tests;
scanf ("%d", &tests);
while (tests --)
{
    read (), moves.clear ();
    bool failed = 0;
    convertToNicerForm (failed);
    if (failed)
    {
        printf ("-1\n");
        continue;
    }
    findCycles ();
    mergeCycles ();
    findCycles ();
    assert (oddCycleRepresentatives.empty ());
    for (auto &currCycle : cycles)
        fixCycle (currCycle);
    print ();
    check ();
}
return 0;
}

Compilation message (stderr)

cat.cpp: In function 'void mergeCycles()':
cat.cpp:82:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=1; i<oddCycleRepresentatives.size (); i+=2)
                   ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cat.cpp: In function 'void fixCycle(std::vector<int>&)':
cat.cpp:116:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int currPos=1; currPos<needXor.size (); currPos+=2)
                         ~~~~~~~^~~~~~~~~~~~~~~~
cat.cpp: In function 'void print()':
cat.cpp:133:52: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' [-Wformat=]
     printf ("%d %d\n", moves.size (), moves.size ());
                        ~~~~~~~~~~~~~               ^
cat.cpp:133:52: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' [-Wformat=]
cat.cpp: In function 'void read()':
cat.cpp:23:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &M), N = M >> 1;
     ~~~~~~~~~~~~~~~~^~~~~~~~~~~~
cat.cpp:29:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &init[i]);
         ~~~~~~^~~~~~~~~~~~~~~~
cat.cpp: In function 'int main()':
cat.cpp:158:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &tests);
 ~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15
• Subtask 5: 35 / 35