Submission #1440935
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int n, a[100010], xx[100010], chk[100010];
vector<vector<pii>> ans;
void f(vector<int> v, int c){
if(v.size() == 1) return;
while(ans.size() <= c) ans.push_back(vector<pii>());
if(v.size() == 2){
ans[c].push_back(pii(v[0], v[1]));
return;
}
if(v.size() == 3){
ans[c].push_back(pii(v[0], v[1]));
vector<int> nv;
nv.push_back(v[0]);
nv.push_back(v[2]);
f(nv, c + 1);
return;
}
int sz = v.size();
ans[c].push_back(pii(v[sz / 2 - 1], v[sz - 1]));
vector<int> lv, rv;
for(int i = 0; i < sz / 2 - 1; i += 2){
if(i + 1 < sz / 2 - 1) ans[c].push_back(pii(v[i], v[i + 1]));
lv.push_back(v[i]);
}
lv.push_back(v[sz / 2 - 1]);
for(int i = sz / 2; i < sz - 1; i += 2){
if(i + 1 < sz) ans[c].push_back(pii(v[i], v[i + 1]));
rv.push_back(v[i]);
}
rv.push_back(v[sz - 1]);
f(lv, c + 1);
f(rv, c + 1);
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", a + i);
xx[i] = a[i];
}
sort(xx + 1, xx + n + 1);
for(int i = 1; i <= n; i++){
a[i] = int(lower_bound(xx + 1, xx + n + 1, a[i]) - xx);
}
for(int i = 1; i <= n; i++){
if(chk[i]) continue;
vector<int> v;
for(int t = i; !chk[t]; t = a[t]){
chk[t] = 1;
v.push_back(t);
}
f(v, 0);
}
printf("%d\n", ans.size());
for(auto &v : ans){
printf("%d ", v.size());
for(int i = 0; i < int(v.size()) - 1; i++){
printf("%d %d ", v[i].first, v[i].second);
}
printf("%d %d\n", v.back().first, v.back().second);
}
}
Submission Info
Submission Time
2017-07-21 11:08:59+0900
Task
D - Distributed Sorting
User
kdh9949
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
1581 Byte
Status
WA
Exec Time
47 ms
Memory
4000 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:59:27: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::vector<std::vector<std::pair<int, int> > >::size_type {aka long unsigned int}’ [-Wformat=]
printf("%d\n", ans.size());
^
./Main.cpp:61:25: 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 ", v.size());
^
./Main.cpp:41:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:43:21: 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
39 ms
3944 KB
hand_07.txt
AC
30 ms
2552 KB
hand_08.txt
AC
30 ms
2552 KB
random_01.txt
WA
47 ms
4000 KB
random_02.txt
WA
47 ms
3944 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
25 ms
1408 KB
three_01.txt
AC
25 ms
1408 KB
three_02.txt
AC
24 ms
1408 KB
three_03.txt
AC
33 ms
1920 KB
three_04.txt
AC
47 ms
2932 KB
three_05.txt
AC
47 ms
2932 KB
trans_01.txt
AC
25 ms
1408 KB
trans_02.txt
AC
25 ms
1408 KB
trans_03.txt
AC
24 ms
1408 KB
trans_04.txt
AC
25 ms
1408 KB
trans_05.txt
AC
29 ms
1792 KB
trans_06.txt
AC
41 ms
2552 KB
two_01.txt
WA
46 ms
3832 KB
two_02.txt
WA
45 ms
3900 KB
two_03.txt
WA
45 ms
3832 KB