oj.uz

Submission #315172

# Submission time Handle Problem Language Result Execution time Memory
315172 2020-10-22T03:48:12 Z daniel920712 Cat (info1cup19_cat) C++14
51.25 / 100
 865 ms 24144 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,con=0,t;
    scanf("%d",&T);
    while(T--)
    {
        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)
                {
                    continue;
                    t=1;
                    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
                {
                    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(N-x+1==y)
                {
                    t=1;
                    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
                {
                    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;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:114: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=]
  114 |             printf("%d %d\n",ans.size(),ans.size());
      |                     ~^       ~~~~~~~~~~
      |                      |               |
      |                      int             std::vector<std::pair<int, int> >::size_type {aka long unsigned int}
      |                     %ld
cat.cpp:114: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=]
  114 |             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,con=0,t;
      |                        ^
cat.cpp:13:32: warning: variable 't' set but not used [-Wunused-but-set-variable]
   13 |     int T,x,y,ok=1,N,i,j,con=0,t;
      |                                ^
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:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |         scanf("%d",&N);
      |         ~~~~~^~~~~~~~~
cat.cpp:24:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |             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 29 ms 544 KB Output is correct
2 Correct 29 ms 504 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 29 ms 544 KB Output is correct
3 Correct 29 ms 504 KB Output is correct
4 Partially correct 37 ms 768 KB Valid reconstruction
5 Partially correct 14 ms 512 KB Valid reconstruction
6 Partially correct 11 ms 512 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 544 KB Output is correct
2 Correct 29 ms 504 KB Output is correct
3 Correct 644 ms 13424 KB Output is correct
4 Correct 617 ms 12140 KB Output is correct
5 Correct 698 ms 15224 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 29 ms 544 KB Output is correct
3 Correct 29 ms 504 KB Output is correct
4 Partially correct 37 ms 768 KB Valid reconstruction
5 Partially correct 14 ms 512 KB Valid reconstruction
6 Partially correct 11 ms 512 KB Valid reconstruction
7 Correct 644 ms 13424 KB Output is correct
8 Correct 617 ms 12140 KB Output is correct
9 Correct 698 ms 15224 KB Output is correct
10 Partially correct 784 ms 18928 KB Valid reconstruction
11 Partially correct 698 ms 14448 KB Valid reconstruction
12 Partially correct 788 ms 20964 KB Valid reconstruction
13 Partially correct 865 ms 24144 KB Valid reconstruction
14 Partially correct 789 ms 19804 KB Valid reconstruction