Submission #1440941

---

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 - 1) 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

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