Submission #315511

#	Time	Username	Problem	Language	Result	Execution time	Memory
315511		daniel920712	Cat (info1cup19_cat)	C++14	100 / 100	710 ms	16720 KiB

cat

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;
int all[3000005];
int where[3000005];
vector < pair < int , int > > ans;
stack < int > how;
int main()
{
    int T,x,y,ok=1,N,i,j,con=0,t,tt=0;
    scanf("%d",&T);
    while(T--)
    {
        while(!how.empty()) how.pop();
        con=0;
        t=0;
        ok=1;
        ans.clear();
        scanf("%d",&N);
        for(i=1;i<=N;i++)
        {
            scanf("%d",&all[i]);
            where[all[i]]=i;
        }

        for(i=1;i<=N/2;i++)
        {
            if(all[i]!=i)
            {
                x=i;
                y=where[i];
                if(N-x+1!=y)
                {
                    con++;
                    swap(all[x],all[y]);
                    where[all[x]]=x;
                    where[all[y]]=y;
                    ans.push_back(make_pair(x,y));
                    swap(all[N-x+1],all[N-y+1]);
                    where[all[N-x+1]]=N-x+1;
                    where[all[N-y+1]]=N-y+1;
                    if(all[N-i+1]!=N-i+1) break;
                }

            }
            else if(all[N-i+1]!=N-i+1) break;

        }
        for(i=1;i<=N/2;i++)
        {
            if(all[i]!=i)
            {
                x=i;
                y=where[i];
                if(x==N-y+1)
                {
                    if(how.empty()) how.push(i);
                    else
                    {
                        ans.push_back(make_pair(i,how.top()));

                        swap(all[i],all[how.top()]);
                        where[all[i]]=i;
                        where[all[how.top()]]=how.top();

                        swap(all[N-i+1],all[N-how.top()+1]);
                        where[all[N-i+1]]=N-i+1;
                        where[all[N-how.top()+1]]=N-how.top()+1;
                        how.pop();
                    }
                }


            }
        }
        for(i=1;i<=N/2;i++)
        {
            if(all[i]!=i)
            {
                x=i;
                y=where[i];
                if(N-x+1!=y)
                {
                    con++;
                    swap(all[x],all[y]);
                    where[all[x]]=x;
                    where[all[y]]=y;
                    ans.push_back(make_pair(x,y));
                    swap(all[N-x+1],all[N-y+1]);
                    where[all[N-x+1]]=N-x+1;
                    where[all[N-y+1]]=N-y+1;
                    if(all[N-i+1]!=N-i+1) break;
                }

            }
            else if(all[N-i+1]!=N-i+1) break;

        }
        con+=tt%2;
        for(i=1;i<=N;i++) if(all[i]!=i) ok=0;
        if(ok)
        {
            printf("%d %d\n",ans.size(),ans.size());
            for(auto i:ans) printf("%d %d\n",i.first,i.second);
        }
        else printf("-1\n");

    }
    return 0;
}

Compilation message (stderr)

cat.cpp: In function 'int main()':
cat.cpp:108:22: 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=]
  108 |             printf("%d %d\n",ans.size(),ans.size());
      |                     ~^       ~~~~~~~~~~
      |                      |               |
      |                      int             std::vector<std::pair<int, int> >::size_type {aka long unsigned int}
      |                     %ld
cat.cpp:108:25: 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=]
  108 |             printf("%d %d\n",ans.size(),ans.size());
      |                        ~^               ~~~~~~~~~~
      |                         |                       |
      |                         int                     std::vector<std::pair<int, int> >::size_type {aka long unsigned int}
      |                        %ld
cat.cpp:15:24: warning: unused variable 'j' [-Wunused-variable]
   15 |     int T,x,y,ok=1,N,i,j,con=0,t,tt=0;
      |                        ^
cat.cpp:15:32: warning: variable 't' set but not used [-Wunused-but-set-variable]
   15 |     int T,x,y,ok=1,N,i,j,con=0,t,tt=0;
      |                                ^
cat.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |     scanf("%d",&T);
      |     ~~~~~^~~~~~~~~
cat.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |         scanf("%d",&N);
      |         ~~~~~^~~~~~~~~
cat.cpp:27:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |             scanf("%d",&all[i]);
      |             ~~~~~^~~~~~~~~~~~~~

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