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 |
|
|
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 |