Submission #1440982
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]);
//a[i] = i-1; if(a[i] == 0) a[i] = N;
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;
for(int j=0; j+3<chain.size(); j+=4){
print[ans].pb(chain[j+1]);
print[ans].pb(chain[j+2]);
swap(a[chain[j+1]],a[chain[j+2]]);
print[ans].pb(chain[j+3]);
print[ans].pb(chain[j]);
swap(a[chain[j+3]],a[chain[j]]);
x = j+3;
}
x++;
for(int j=x; j+1<chain.size(); 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:52:08+0900
Task
D - Distributed Sorting
User
suhgyuho
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
1969 Byte
Status
WA
Exec Time
87 ms
Memory
5616 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:75: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
79 ms
5616 KB
hand_07.txt
AC
34 ms
4600 KB
hand_08.txt
AC
34 ms
4600 KB
random_01.txt
WA
84 ms
5580 KB
random_02.txt
WA
87 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
30 ms
3576 KB
three_02.txt
AC
30 ms
3576 KB
three_03.txt
AC
38 ms
3960 KB
three_04.txt
AC
53 ms
4856 KB
three_05.txt
AC
53 ms
4856 KB
trans_01.txt
AC
26 ms
3576 KB
trans_02.txt
AC
26 ms
3576 KB
trans_03.txt
AC
26 ms
3576 KB
trans_04.txt
AC
26 ms
3576 KB
trans_05.txt
AC
31 ms
3832 KB
trans_06.txt
AC
46 ms
4600 KB
two_01.txt
WA
82 ms
5500 KB
two_02.txt
WA
82 ms
5480 KB
two_03.txt
WA
82 ms
5460 KB