oj.uz

Submission #315504

# Submission time Handle Problem Language Result Execution time Memory
315504 2020-10-23T02:17:09 Z daniel920712 Cat (info1cup19_cat) C++14
51.25 / 100
 728 ms 14956 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)
                {
                    tt++;
                    if(tt%2==0) con++;
                    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:67: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=]
   67 |             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 6 ms 384 KB Valid reconstruction

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 512 KB Output is correct
2 Correct 31 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 31 ms 512 KB Output is correct
3 Correct 31 ms 504 KB Output is correct
4 Partially correct 36 ms 632 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 31 ms 512 KB Output is correct
2 Correct 31 ms 504 KB Output is correct
3 Correct 699 ms 13356 KB Output is correct
4 Correct 666 ms 12268 KB Output is correct
5 Correct 706 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 31 ms 512 KB Output is correct
3 Correct 31 ms 504 KB Output is correct
4 Partially correct 36 ms 632 KB Valid reconstruction
5 Partially correct 13 ms 512 KB Valid reconstruction
6 Partially correct 10 ms 384 KB Valid reconstruction
7 Correct 699 ms 13356 KB Output is correct
8 Correct 666 ms 12268 KB Output is correct
9 Correct 706 ms 14956 KB Output is correct
10 Partially correct 691 ms 11928 KB Valid reconstruction
11 Partially correct 645 ms 10304 KB Valid reconstruction
12 Partially correct 692 ms 13020 KB Valid reconstruction
13 Partially correct 728 ms 14956 KB Valid reconstruction
14 Partially correct 685 ms 12768 KB Valid reconstruction