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
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
AC × 3
AC × 31
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