oj.uz

Submission #315141

# Submission time Handle Problem Language Result Execution time Memory
315141 2020-10-22T03:18:37 Z daniel920712 Cat (info1cup19_cat) C++14
51.25 / 100
 722 ms 15080 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>

using namespace std;
int all[3000005];
int where[3000005];
vector < pair < int , int > > ans;
int main()
{
    int T,x,y,ok=1,N,i,j;
    scanf("%d",&T);
    while(T--)
    {
        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)
                {
                    if(x+1==y) break;
                    swap(all[x],all[x+1]);
                    where[all[x]]=x;
                    where[all[x+1]]=x+1;
                    ans.push_back(make_pair(x,x+1));
                    swap(all[N-x+1],all[N-x]);
                    where[all[N-x+1]]=N-x+1;
                    where[all[N-x]]=N-x;
                    i--;
                }
                else
                {
                    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)
                    {
                        //printf("aa %d %d\n",i,all[N-i+1]);
                        break;
                    }

                }


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

        }
        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

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

Subtask #1
5.25 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 384 KB Valid reconstruction

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 512 KB Output is correct
2 Correct 31 ms 512 KB Output is correct

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 384 KB Valid reconstruction
2 Correct 30 ms 512 KB Output is correct
3 Correct 31 ms 512 KB Output is correct
4 Partially correct 33 ms 640 KB Valid reconstruction
5 Partially correct 12 ms 512 KB Valid reconstruction
6 Partially correct 10 ms 384 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 512 KB Output is correct
2 Correct 31 ms 512 KB Output is correct
3 Correct 695 ms 13424 KB Output is correct
4 Correct 656 ms 12136 KB Output is correct
5 Correct 695 ms 14956 KB Output is correct

Subtask #5
12.25 / 35.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 384 KB Valid reconstruction
2 Correct 30 ms 512 KB Output is correct
3 Correct 31 ms 512 KB Output is correct
4 Partially correct 33 ms 640 KB Valid reconstruction
5 Partially correct 12 ms 512 KB Valid reconstruction
6 Partially correct 10 ms 384 KB Valid reconstruction
7 Correct 695 ms 13424 KB Output is correct
8 Correct 656 ms 12136 KB Output is correct
9 Correct 695 ms 14956 KB Output is correct
10 Partially correct 666 ms 12024 KB Valid reconstruction
11 Partially correct 635 ms 10100 KB Valid reconstruction
12 Partially correct 671 ms 13160 KB Valid reconstruction
13 Partially correct 722 ms 15080 KB Valid reconstruction
14 Partially correct 667 ms 12768 KB Valid reconstruction