oj.uz

Submission #690574

# Submission time Handle Problem Language Result Execution time Memory
690574 2023-01-30T09:54:00 Z alexdd Cat (info1cup19_cat) C++17
25 / 100
 937 ms 29372 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()
{
    sol.clear();
    for(int i=1;i<=n/2;i++)
    {
        if(p[i]==i)
            continue;
        da_swap(i, unde[i]);
    }
    bool possible=1;
    for(int i=n/2;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];
            unde[p[i]]=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:42: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]
   42 |         for(int i=0;i<sol.size();i++)
      |                     ~^~~~~~~~~~~

Subtask #1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 340 KB Wrong answer
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 592 KB Output is correct
2 Correct 42 ms 880 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 340 KB Wrong answer
2 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 592 KB Output is correct
2 Correct 42 ms 880 KB Output is correct
3 Correct 929 ms 28244 KB Output is correct
4 Correct 871 ms 26948 KB Output is correct
5 Correct 937 ms 29372 KB Output is correct

Subtask #5
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 340 KB Wrong answer
2 Halted 0 ms 0 KB -