oj.uz

Submission #315170

# Submission time Handle Problem Language Result Execution time Memory
315170 2020-10-22T03:46:12 Z daniel920712 Cat (info1cup19_cat) C++14
51.25 / 100
 744 ms 15088 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)
                {
                    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",con+t,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: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",con+t,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: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 30 ms 512 KB Output is correct
2 Correct 30 ms 512 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 30 ms 512 KB Output is correct
3 Correct 30 ms 512 KB Output is correct
4 Partially correct 34 ms 640 KB Valid reconstruction
5 Partially correct 13 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 30 ms 512 KB Output is correct
3 Correct 677 ms 13544 KB Output is correct
4 Correct 654 ms 12252 KB Output is correct
5 Correct 699 ms 15088 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 30 ms 512 KB Output is correct
3 Correct 30 ms 512 KB Output is correct
4 Partially correct 34 ms 640 KB Valid reconstruction
5 Partially correct 13 ms 512 KB Valid reconstruction
6 Partially correct 10 ms 384 KB Valid reconstruction
7 Correct 677 ms 13544 KB Output is correct
8 Correct 654 ms 12252 KB Output is correct
9 Correct 699 ms 15088 KB Output is correct
10 Partially correct 672 ms 12020 KB Valid reconstruction
11 Partially correct 628 ms 10024 KB Valid reconstruction
12 Partially correct 682 ms 13288 KB Valid reconstruction
13 Partially correct 744 ms 14960 KB Valid reconstruction
14 Partially correct 667 ms 12652 KB Valid reconstruction