oj.uz

Submission #315503

# Submission time Handle Problem Language Result Execution time Memory
315503 2020-10-23T02:10:40 Z daniel920712 Cat (info1cup19_cat) C++14
51.25 / 100
 753 ms 24684 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,tt=0;
    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)
                {
                    con++;
                    tt++;
                    if(tt%2==0) con++;
                    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;

        }
        con+=tt%2;
        for(i=1;i<=N;i++) if(all[i]!=i) ok=0;
        if(ok)
        {
            printf("%d %d\n",con,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:69: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=]
   69 |             printf("%d %d\n",con,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,tt=0;
      |                        ^
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,tt=0;
      |                                ^
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 7 ms 384 KB Valid reconstruction

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1048 KB Output is correct
2 Correct 31 ms 1020 KB Output is correct

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 384 KB Valid reconstruction
2 Correct 34 ms 1048 KB Output is correct
3 Correct 31 ms 1020 KB Output is correct
4 Partially correct 35 ms 1272 KB Valid reconstruction
5 Partially correct 13 ms 640 KB Valid reconstruction
6 Partially correct 11 ms 640 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1048 KB Output is correct
2 Correct 31 ms 1020 KB Output is correct
3 Correct 714 ms 22896 KB Output is correct
4 Correct 684 ms 21864 KB Output is correct
5 Correct 731 ms 24684 KB Output is correct

Subtask #5
12.25 / 35.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 384 KB Valid reconstruction
2 Correct 34 ms 1048 KB Output is correct
3 Correct 31 ms 1020 KB Output is correct
4 Partially correct 35 ms 1272 KB Valid reconstruction
5 Partially correct 13 ms 640 KB Valid reconstruction
6 Partially correct 11 ms 640 KB Valid reconstruction
7 Correct 714 ms 22896 KB Output is correct
8 Correct 684 ms 21864 KB Output is correct
9 Correct 731 ms 24684 KB Output is correct
10 Partially correct 691 ms 21004 KB Valid reconstruction
11 Partially correct 649 ms 19188 KB Valid reconstruction
12 Partially correct 703 ms 22124 KB Valid reconstruction
13 Partially correct 753 ms 24256 KB Valid reconstruction
14 Partially correct 692 ms 21744 KB Valid reconstruction