Submission #1529430

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
int N;
LL X[100001];
bool used[100001];
map<LL,int> m;
typedef pair<int,int>P;
vector<P>v;
vector<P>v2;
vector<LL>vv;
LL Y[100001];

void dfs(LL x,int c){
//cout<<x<<"xxx"<<endl;
   used[x]=true;
   //正しい場所にいる
   if(X[x]==x){
      return;
   }
   LL y=Y[x];//交換先(xの値を持っている人)
   if(c==0){
      v.push_back(P{x+1,y+1});
      X[y]=X[x];
   }else{
      v2.push_back(P{x+1,y+1});
      X[y]=X[x];
   }
   //cout<<"dfs"<<endl;
   dfs(y,1-c);
}

int main(){
    int N;
    cin>>N;
    REP(i,N){
        cin>>X[i];
        vv.push_back(X[i]);
    }
    sort(vv.begin(),vv.end());
    REP(i,N){
        m[vv[i]]=i;
        //cout<<vv[i]<<" "<<m[vv[i]]<<endl;
    }
    REP(i,N){
        X[i]=m[X[i]];
        //cout<<"m"<<X[i]<<" "<<m[X[i]]<<endl;
    }
    REP(i,N){
       Y[X[i]]=i;
    }
    
    REP(i,N){
        used[i]=false;
    }
    REP(i,N){
        if(used[i]==false){
        //cout<<m[X[i]]<<endl;
           dfs(i,0);
        }
    }
    if(v.size()==0){
       cout<<0<<endl;
    }else if(v2.size()==0){
       cout<<1<<endl;
       cout<<v.size()<<" ";
       REP(i,v.size()){
          cout<<v[i].first<<" "<<v[i].second;
          if(i==v.size()-1){
             cout<<endl;
          }else{
             cout<<" ";
          }
       }
    }else{
       cout<<2<<endl;
       cout<<v.size()<<" ";
       REP(i,v.size()){
          cout<<v[i].first<<" "<<v[i].second;
          if(i==v.size()-1){
             cout<<endl;
          }else{
             cout<<" ";
          }
       }
       cout<<v2.size()<<" ";
       REP(i,v2.size()){
          cout<<v2[i].first<<" "<<v2[i].second;
          if(i==v2.size()-1){
             cout<<endl;
          }else{
             cout<<" ";
          }
       }
    }
    return(0);
}

Submission Info

Judge Result