Submission #1440967
Source Code Expand
#include <bits/stdc++.h>
#include <unistd.h>
#define pii pair<int,int>
#define pll pair<lld,lld>
#define pb push_back
#define next nextt
#define left leftt
#define right rightt
#define lld long long
#define Inf 1000000000
#define Mod 1000000007
#define Linf 1000000000000000000LL
#define get gett
using namespace std;
int N,ans;
int a[100002];
bool check[100002];
vector<int> print[100002],X;
int main(){
//freopen("input.txt","r",stdin);
scanf("%d",&N);
for(int i=1; i<=N; i++){
scanf("%d",&a[i]);
X.pb(a[i]);
}
sort(X.begin(),X.end());
X.erase(unique(X.begin(),X.end()),X.end());
if(X.size() != N) while(true);
for(int i=1; i<=N; i++){
a[i] = lower_bound(X.begin(),X.end(),a[i])-X.begin()+1;
}
while(1){
for(int i=1; i<=N; i++) check[i] = false;
for(int i=1; i<=N; i++){
if(check[i]) continue;
vector<int> chain;
int x = i;
while(!check[x]){
check[x] = true;
chain.pb(x);
x = a[x];
}
if(chain.size() == 1) continue;
x = -1;
int y = chain.size();
for(int j=0,cnt=1; cnt*4<chain.size(); j+=3){
cnt++;
print[ans].pb(chain[j]);
print[ans].pb(chain[j+1]);
swap(a[chain[j]],a[chain[j+1]]);
print[ans].pb(chain[j+2]);
print[ans].pb(chain[chain.size()-j/3-1]);
swap(a[chain[j+2]],a[chain[chain.size()-j/3-1]]);
x = j+2; y = chain.size()-j/3-1;
}
x++;
for(int j=x; j+1<y; j+=2){
print[ans].pb(chain[j]);
print[ans].pb(chain[j+1]);
swap(a[chain[j]],a[chain[j+1]]);
}
}
if(print[ans].size() == 0) break;
ans++;
}
for(int i=1; i<=N; i++){
if(i != a[i]) while(true);
}
printf("%d\n",ans);
for(int i=0; i<ans; i++){
printf("%d",print[i].size()/2);
for(int j=0; j<print[i].size(); j++){
printf(" %d",print[i][j]);
}
puts("");
}
return 0;
}
Submission Info
Submission Time
2017-07-21 11:36:19+0900
Task
D - Distributed Sorting
User
suhgyuho
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2038 Byte
Status
WA
Exec Time
62 ms
Memory
5708 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:76:32: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::vector<int>::size_type {aka long unsigned int}’ [-Wformat=]
printf("%d",print[i].size()/2);
^
./Main.cpp:25:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
^
./Main.cpp:27: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
2 ms
2560 KB
hand_02.txt
AC
2 ms
2560 KB
hand_03.txt
AC
2 ms
2560 KB
hand_04.txt
AC
2 ms
2560 KB
hand_05.txt
AC
2 ms
2560 KB
hand_06.txt
WA
53 ms
5616 KB
hand_07.txt
AC
34 ms
4600 KB
hand_08.txt
AC
34 ms
4600 KB
random_01.txt
WA
62 ms
5708 KB
random_02.txt
WA
62 ms
5616 KB
sample-01.txt
AC
2 ms
2560 KB
sample-02.txt
AC
2 ms
2560 KB
sample-03.txt
AC
2 ms
2560 KB
sorted_01.txt
AC
22 ms
3576 KB
three_01.txt
AC
29 ms
3576 KB
three_02.txt
AC
29 ms
3576 KB
three_03.txt
AC
37 ms
3960 KB
three_04.txt
AC
53 ms
4856 KB
three_05.txt
AC
52 ms
4856 KB
trans_01.txt
AC
25 ms
3576 KB
trans_02.txt
AC
25 ms
3576 KB
trans_03.txt
AC
25 ms
3576 KB
trans_04.txt
AC
26 ms
3576 KB
trans_05.txt
AC
30 ms
3832 KB
trans_06.txt
AC
45 ms
4600 KB
two_01.txt
WA
60 ms
5680 KB
two_02.txt
WA
60 ms
5640 KB
two_03.txt
WA
60 ms
5624 KB