Submission #1159777
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
#define ALL(x) x.begin(),x.end()
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;
int N;
bool vis [100001];
vector<int> A;
void dfs(int curr,vector<int>& v)
{
vis [curr] = true;
v.push_back(curr);
if(vis [A [curr]] == false){
dfs(A [curr],v);
}
}
int main()
{
scanf("%d",&N);
A.assign(N + 1,0);
map<int,int> mp;
FOR(i,1,N + 1){
scanf("%d",&A [i]);
mp [A [i]];
}
{
int id = 1;
for(auto& it : mp){
it.second = id;
id++;
}
}
FOR(i,1,N + 1){
A [i] = mp [A [i]];
}
vector< vector<int> > ans;
FOR(t,0,2){
bool flag = true;
memset(vis,0,sizeof(vis));
FOR(i,1,N + 1) if(vis [i] == false){
vector<int> v;
dfs(i,v);
FOR(i,0,v.size() / 2){
if(flag){
ans.push_back({});
flag = false;
}
ans.back().push_back(v [i]);
ans.back().push_back(v [v.size() - 1 - i]);
swap(A [v [i]],A [v [v.size() - 1 - i]]);
}
}
}
printf("%lu\n",ans.size());
FOR(i,0,ans.size()){
printf("%lu ",ans [i].size() / 2);
FOR(j,0,ans [i].size()){
printf("%d%s",ans [i] [j],j == ans [i].size() - 1 ? "\n" : " ");
}
}
return 0;
}
Submission Info
Submission Time
2017-03-13 09:42:44+0900
Task
D - Distributed Sorting
User
gigime
Language
C++14 (GCC 5.4.1)
Score
100
Code Size
1421 Byte
Status
AC
Exec Time
131 ms
Memory
10992 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./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:29: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
100 / 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
384 KB
hand_02.txt
AC
1 ms
384 KB
hand_03.txt
AC
1 ms
384 KB
hand_04.txt
AC
1 ms
384 KB
hand_05.txt
AC
1 ms
384 KB
hand_06.txt
AC
82 ms
10992 KB
hand_07.txt
AC
72 ms
6520 KB
hand_08.txt
AC
72 ms
6520 KB
random_01.txt
AC
119 ms
10316 KB
random_02.txt
AC
115 ms
10992 KB
sample-01.txt
AC
1 ms
384 KB
sample-02.txt
AC
1 ms
384 KB
sample-03.txt
AC
1 ms
384 KB
sorted_01.txt
AC
57 ms
5376 KB
three_01.txt
AC
52 ms
5376 KB
three_02.txt
AC
45 ms
5376 KB
three_03.txt
AC
67 ms
5888 KB
three_04.txt
AC
110 ms
6776 KB
three_05.txt
AC
101 ms
6904 KB
trans_01.txt
AC
54 ms
5376 KB
trans_02.txt
AC
48 ms
5376 KB
trans_03.txt
AC
43 ms
5376 KB
trans_04.txt
AC
46 ms
5376 KB
trans_05.txt
AC
62 ms
5760 KB
trans_06.txt
AC
102 ms
6520 KB
two_01.txt
AC
112 ms
8508 KB
two_02.txt
AC
122 ms
9404 KB
two_03.txt
AC
131 ms
8464 KB