Submission #1440943
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(vector<int> &arr){
for(int i=0; arr.size() != 1; i++){
vector<int> nxt;
for(int j=0; j+1<arr.size(); j+=2){
swap(a[arr[j]], a[arr[j+1]]);
steps[i].push_back(pi(arr[j], arr[j+1]));
nxt.push_back(arr[j]);
}
if(arr.size() % 2) nxt.push_back(arr.back());
arr = nxt;
}
}
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;
}
int b[100005];
for(int i=1; i<=n; i++){
b[a[i]] = i;
}
memcpy(b, a, sizeof(b));
for(int i=1; i<=n; i++){
if(!vis[i]){
vector<int> arr;
for(int j=i; !vis[j]; j=a[j]){
vis[j] = 1;
arr.push_back(j);
}
solve(arr);
}
}
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 11:13:13+0900
Task
D - Distributed Sorting
User
koosaga
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
1308 Byte
Status
WA
Exec Time
47 ms
Memory
3960 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:55: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:26:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:28: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
AC
1 ms
256 KB
hand_06.txt
WA
39 ms
3440 KB
hand_07.txt
AC
30 ms
2552 KB
hand_08.txt
AC
30 ms
2552 KB
random_01.txt
WA
47 ms
3660 KB
random_02.txt
WA
47 ms
3440 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
21 ms
1528 KB
three_01.txt
AC
21 ms
1528 KB
three_02.txt
AC
21 ms
1528 KB
three_03.txt
AC
30 ms
1912 KB
three_04.txt
AC
46 ms
3320 KB
three_05.txt
AC
46 ms
3320 KB
trans_01.txt
AC
21 ms
1528 KB
trans_02.txt
AC
21 ms
1528 KB
trans_03.txt
AC
21 ms
1528 KB
trans_04.txt
AC
22 ms
1528 KB
trans_05.txt
AC
26 ms
1784 KB
trans_06.txt
AC
41 ms
2552 KB
two_01.txt
WA
45 ms
3604 KB
two_02.txt
WA
44 ms
3960 KB
two_03.txt
WA
44 ms
3704 KB