Submission #1514351


Source Code Expand

 #include<bits/stdc++.h>
 using namespace std;
#define INF 1000000000
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
typedef long long LL;
int N;
LL X[100001];
LL pos[100001];
bool used[100001];
vector<LL>v;
typedef pair<LL,LL>P;
vector<P>v2[1000];
map<LL,LL>m;
int main(){
    cin>>N;
    REP(i,N){
        cin>>X[i];
        v.push_back(X[i]);
    }
    sort(v.begin(),v.end());
    REP(i,v.size()){
        m[v[i]]=i;
    }
    REP(i,N){
        X[i]=m[X[i]];
        pos[X[i]]=i;
    }
    int count=0;
    while(1){
       REP(i,N){
           used[i]=false;
       }
       bool check=true;
       REP(i,N){
           //i 自分の値
           //pos[i] 自分の値の位置
           //X[i] i番目の値
           //pos[X[i]] X[i]の位置
           if(pos[i]!=i){
              check=false;
              int re=X[i];
              int re_pos=pos[X[i]];
              if(used[i]==false&&used[X[i]]==false){
                 used[i]=true;
                 used[X[i]]=true;
                 v2[count].push_back(P(re_pos+1,pos[i]+1));
                 //swap
                 X[i]=i;
                 X[pos[i]]=re;
                 pos[re]=pos[i];
                 pos[i]=re_pos;
              }
           }
       }
       if(check)break;
       count++;
    }
    cout<<count<<endl;
    REP(i,count){
        cout<<v2[i].size()<<" ";
        REP(j,v2[i].size()){
            cout<<v2[i][j].first<<" "<<v2[i][j].second;
            if(j!=v2[i].size()-1){
               cout<<" ";
            }else{
               cout<<endl;
            }
        }
    }
    
    return 0;
}

Submission Info

Submission Time
Task D - Distributed Sorting
User rapurasu
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1666 Byte
Status WA
Exec Time 145 ms
Memory 11764 KB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 3
AC × 25
WA × 6
Set Name Test Cases
sample sample-01.txt, sample-02.txt, sample-03.txt
All sample-01.txt, sample-02.txt, sample-03.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, random_01.txt, random_02.txt, sample-01.txt, sample-02.txt, sample-03.txt, sorted_01.txt, three_01.txt, three_02.txt, three_03.txt, three_04.txt, three_05.txt, trans_01.txt, trans_02.txt, trans_03.txt, trans_04.txt, trans_05.txt, trans_06.txt, two_01.txt, two_02.txt, two_03.txt
Case Name Status Exec Time Memory
hand_01.txt AC 1 ms 256 KB
hand_02.txt AC 1 ms 256 KB
hand_03.txt AC 1 ms 256 KB
hand_04.txt AC 1 ms 256 KB
hand_05.txt AC 1 ms 256 KB
hand_06.txt WA 109 ms 11764 KB
hand_07.txt AC 91 ms 10484 KB
hand_08.txt AC 89 ms 10484 KB
random_01.txt WA 145 ms 11764 KB
random_02.txt WA 145 ms 11764 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB
sorted_01.txt AC 81 ms 8948 KB
three_01.txt AC 80 ms 8948 KB
three_02.txt AC 80 ms 8948 KB
three_03.txt AC 97 ms 9844 KB
three_04.txt AC 123 ms 10996 KB
three_05.txt AC 124 ms 10996 KB
trans_01.txt AC 80 ms 8948 KB
trans_02.txt AC 81 ms 8948 KB
trans_03.txt AC 81 ms 8948 KB
trans_04.txt AC 82 ms 8948 KB
trans_05.txt AC 90 ms 9460 KB
trans_06.txt AC 119 ms 10484 KB
two_01.txt WA 132 ms 11764 KB
two_02.txt WA 133 ms 11764 KB
two_03.txt WA 133 ms 11764 KB