Submission #690568

# Submission time Handle Problem Language Result Execution time Memory
690568 2023-01-30T09:50:23 Z alexdd Cat (info1cup19_cat) C++17
0 / 100
1000 ms 37844 KB
#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
int n;
int p[200001];
int unde[200001];
bool subtask=1;
vector<pair<int,int>> sol;
void da_swap(int x, int y)
{
    sol.push_back({x,y});
    int a=n-x+1,b=n-y+1;
    swap(unde[p[x]], unde[p[y]]);
    swap(p[x], p[y]);

    swap(unde[p[a]], unde[p[b]]);
    swap(p[a], p[b]);
}
void subtask_half()
{
    for(int i=1;i<=n;i++)
        unde[p[i]]=i;
    for(int i=1;i<=n/2;i++)
    {
        ///pune i pe pozitia i
        if(p[i]==i)
            continue;
        da_swap(i, unde[i]);
    }
    bool possible=1;
    for(int i=1;i<=n;i++)
        if(p[i]!=i)
        {
            possible=0;
            break;
        }
    if(!possible)
    {
        cout<<-1<<"\n";
    }
    else
    {
        cout<<sol.size()<<" "<<sol.size()<<"\n";
        for(int i=0;i<sol.size();i++)
            cout<<sol[i].first<<" "<<sol[i].second<<"\n";
    }
    return;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        subtask=1;
        for(int i=1;i<=n;i++)
        {
            cin>>p[i];
            if(i<=n/2 && p[i]>n/2)
                subtask=0;
        }
        subtask_half();
    }
    return 0;
}

Compilation message

cat.cpp: In function 'void subtask_half()':
cat.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int i=0;i<sol.size();i++)
      |                     ~^~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 880 ms 24652 KB Wrong answer
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 37844 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 880 ms 24652 KB Wrong answer
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 37844 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 880 ms 24652 KB Wrong answer
2 Halted 0 ms 0 KB -