Submission #1441125
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 100005;
int n, a[MAXN], vis[MAXN];
vector<pi> steps[20];
void solve(deque<int> &arr){
if(arr.size() == 1) return;
if(arr.size() == 2){
steps[0].push_back(pi(arr[0], arr[1]));
return;
}
if(arr.size() & 1){
steps[0].push_back(pi(arr.back(), arr.front()));
arr.pop_front();
}
while(arr.size() >= 4){
steps[0].push_back(pi(arr[arr.size() - 2], arr.front()));
steps[1].push_back(pi(arr.back(), arr.front()));
arr.pop_front();
arr.pop_back();
}
steps[0].push_back(pi(arr[0], arr[1]));
}
vector<int> v;
int main(){
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
v.push_back(a[i]);
}
sort(v.begin(), v.end());
for(int i=1; i<=n; i++){
a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
}
for(int i=1; i<=n; i++){
if(!vis[i]){
deque<int> arr;
for(int j=i; !vis[j]; j=a[j]){
vis[j] = 1;
arr.push_back(j);
}
solve(arr);
}
}
for(auto &i : steps[0]) swap(a[i.first], a[i.second]);
for(auto &i : steps[1]) swap(a[i.first], a[i.second]);
assert(is_sorted(a+1, a+n+1));
for(int i=0; ; i++){
if(steps[i].empty()){
printf("%d\n", i);
for(int j=0; j<i; j++){
printf("%d", steps[j].size());
for(auto &k : steps[j]) printf(" %d %d", k.first, k.second);
puts("");
}
return 0;
}
}
}
Submission Info
Submission Time
2017-07-21 13:56:52+0900
Task
D - Distributed Sorting
User
koosaga
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
1486 Byte
Status
WA
Exec Time
47 ms
Memory
3960 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:58:33: 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=]
printf("%d", steps[j].size());
^
./Main.cpp:32:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:34:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
^
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
WA
1 ms
256 KB
hand_06.txt
WA
38 ms
3500 KB
hand_07.txt
AC
32 ms
2552 KB
hand_08.txt
AC
32 ms
2552 KB
random_01.txt
WA
47 ms
3788 KB
random_02.txt
WA
47 ms
3872 KB
sample-01.txt
WA
1 ms
256 KB
sample-02.txt
AC
1 ms
256 KB
sample-03.txt
AC
1 ms
256 KB
sorted_01.txt
AC
31 ms
1528 KB
three_01.txt
WA
25 ms
1528 KB
three_02.txt
WA
28 ms
1528 KB
three_03.txt
WA
38 ms
2040 KB
three_04.txt
WA
44 ms
2804 KB
three_05.txt
WA
44 ms
2804 KB
trans_01.txt
AC
29 ms
1528 KB
trans_02.txt
AC
26 ms
1528 KB
trans_03.txt
AC
27 ms
1528 KB
trans_04.txt
AC
28 ms
1528 KB
trans_05.txt
AC
35 ms
1784 KB
trans_06.txt
AC
43 ms
2552 KB
two_01.txt
WA
45 ms
3960 KB
two_02.txt
WA
45 ms
3960 KB
two_03.txt
WA
44 ms
3960 KB