Submission #1514326
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<int,int>P; vector<P>v2[30]; map<LL,int>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){ 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 | 1524 Byte |
Status | WA |
Exec Time | 144 ms |
Memory | 10996 KB |
Judge Result
Set Name | sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | ||||||
Status |
|
|
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 | 10996 KB |
hand_07.txt | AC | 90 ms | 10356 KB |
hand_08.txt | AC | 89 ms | 10356 KB |
random_01.txt | WA | 144 ms | 10996 KB |
random_02.txt | WA | 143 ms | 10996 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 | 80 ms | 8948 KB |
three_01.txt | AC | 79 ms | 8948 KB |
three_02.txt | AC | 80 ms | 8948 KB |
three_03.txt | AC | 95 ms | 9460 KB |
three_04.txt | AC | 122 ms | 10740 KB |
three_05.txt | AC | 123 ms | 10740 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 | 81 ms | 8948 KB |
trans_05.txt | AC | 90 ms | 9204 KB |
trans_06.txt | AC | 118 ms | 10356 KB |
two_01.txt | WA | 132 ms | 10996 KB |
two_02.txt | WA | 131 ms | 10996 KB |
two_03.txt | WA | 132 ms | 10996 KB |