oj.uz

Submission #315511

# Submission time Handle Problem Language Result Execution time Memory
315511 2020-10-23T02:32:02 Z daniel920712 Cat (info1cup19_cat) C++14
100 / 100
 710 ms 16720 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;
int all[3000005];
int where[3000005];
vector < pair < int , int > > ans;
stack < int > how;
int main()
{
    int T,x,y,ok=1,N,i,j,con=0,t,tt=0;
    scanf("%d",&T);
    while(T--)
    {
        while(!how.empty()) how.pop();
        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++;
                    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(x==N-y+1)
                {
                    if(how.empty()) how.push(i);
                    else
                    {
                        ans.push_back(make_pair(i,how.top()));

                        swap(all[i],all[how.top()]);
                        where[all[i]]=i;
                        where[all[how.top()]]=how.top();

                        swap(all[N-i+1],all[N-how.top()+1]);
                        where[all[N-i+1]]=N-i+1;
                        where[all[N-how.top()+1]]=N-how.top()+1;
                        how.pop();
                    }
                }


            }
        }
        for(i=1;i<=N/2;i++)
        {
            if(all[i]!=i)
            {
                x=i;
                y=where[i];
                if(N-x+1!=y)
                {
                    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",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:108: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=]
  108 |             printf("%d %d\n",ans.size(),ans.size());
      |                     ~^       ~~~~~~~~~~
      |                      |               |
      |                      int             std::vector<std::pair<int, int> >::size_type {aka long unsigned int}
      |                     %ld
cat.cpp:108: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=]
  108 |             printf("%d %d\n",ans.size(),ans.size());
      |                        ~^               ~~~~~~~~~~
      |                         |                       |
      |                         int                     std::vector<std::pair<int, int> >::size_type {aka long unsigned int}
      |                        %ld
cat.cpp:15:24: warning: unused variable 'j' [-Wunused-variable]
   15 |     int T,x,y,ok=1,N,i,j,con=0,t,tt=0;
      |                        ^
cat.cpp:15:32: warning: variable 't' set but not used [-Wunused-but-set-variable]
   15 |     int T,x,y,ok=1,N,i,j,con=0,t,tt=0;
      |                                ^
cat.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |     scanf("%d",&T);
      |     ~~~~~^~~~~~~~~
cat.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |         scanf("%d",&N);
      |         ~~~~~^~~~~~~~~
cat.cpp:27:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |             scanf("%d",&all[i]);
      |             ~~~~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 560 KB Output is correct
2 Correct 38 ms 512 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 32 ms 560 KB Output is correct
3 Correct 38 ms 512 KB Output is correct
4 Correct 33 ms 1152 KB Output is correct
5 Correct 13 ms 640 KB Output is correct
6 Correct 12 ms 640 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 560 KB Output is correct
2 Correct 38 ms 512 KB Output is correct
3 Correct 684 ms 13388 KB Output is correct
4 Correct 657 ms 12268 KB Output is correct
5 Correct 701 ms 14952 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 32 ms 560 KB Output is correct
3 Correct 38 ms 512 KB Output is correct
4 Correct 33 ms 1152 KB Output is correct
5 Correct 13 ms 640 KB Output is correct
6 Correct 12 ms 640 KB Output is correct
7 Correct 684 ms 13388 KB Output is correct
8 Correct 657 ms 12268 KB Output is correct
9 Correct 701 ms 14952 KB Output is correct
10 Correct 662 ms 13044 KB Output is correct
11 Correct 638 ms 11380 KB Output is correct
12 Correct 684 ms 14956 KB Output is correct
13 Correct 710 ms 16720 KB Output is correct
14 Correct 667 ms 14572 KB Output is correct