oj.uz

Submission #160310

# Submission time Handle Problem Language Result Execution time Memory
160310 2019-10-27T00:52:48 Z model_code Cat (info1cup19_cat) C++17
100 / 100
 781 ms 15340 KB 
/*
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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 504 KB Output is correct
2 Correct 37 ms 632 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB Output is correct
2 Correct 37 ms 504 KB Output is correct
3 Correct 37 ms 632 KB Output is correct
4 Correct 45 ms 632 KB Output is correct
5 Correct 16 ms 504 KB Output is correct
6 Correct 14 ms 376 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 504 KB Output is correct
2 Correct 37 ms 632 KB Output is correct
3 Correct 670 ms 11460 KB Output is correct
4 Correct 647 ms 10976 KB Output is correct
5 Correct 709 ms 14188 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB Output is correct
2 Correct 37 ms 504 KB Output is correct
3 Correct 37 ms 632 KB Output is correct
4 Correct 45 ms 632 KB Output is correct
5 Correct 16 ms 504 KB Output is correct
6 Correct 14 ms 376 KB Output is correct
7 Correct 670 ms 11460 KB Output is correct
8 Correct 647 ms 10976 KB Output is correct
9 Correct 709 ms 14188 KB Output is correct
10 Correct 704 ms 10876 KB Output is correct
11 Correct 641 ms 9228 KB Output is correct
12 Correct 687 ms 13716 KB Output is correct
13 Correct 781 ms 15340 KB Output is correct
14 Correct 714 ms 13528 KB Output is correct