Submission #1441125


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 100005;

int n, a[MAXN], vis[MAXN];
vector<pi> steps[20];

void solve(deque<int> &arr){
	if(arr.size() == 1) return;
	if(arr.size() == 2){
		steps[0].push_back(pi(arr[0], arr[1]));
		return;
	}
	if(arr.size() & 1){
		steps[0].push_back(pi(arr.back(), arr.front()));
		arr.pop_front();
	}
	while(arr.size() >= 4){
		steps[0].push_back(pi(arr[arr.size() - 2], arr.front()));
		steps[1].push_back(pi(arr.back(), arr.front()));
		arr.pop_front();
		arr.pop_back();
	}
	steps[0].push_back(pi(arr[0], arr[1]));
}

vector<int> v;
int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
		v.push_back(a[i]);
	}
	sort(v.begin(), v.end());
	for(int i=1; i<=n; i++){
		a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
	}
	for(int i=1; i<=n; i++){
		if(!vis[i]){
			deque<int> arr;
			for(int j=i; !vis[j]; j=a[j]){
				vis[j] = 1;
				arr.push_back(j);
			}
			solve(arr);
		}
	}
	for(auto &i : steps[0]) swap(a[i.first], a[i.second]);
	for(auto &i : steps[1]) swap(a[i.first], a[i.second]);
	assert(is_sorted(a+1, a+n+1));
	for(int i=0; ; i++){
		if(steps[i].empty()){
			printf("%d\n", i);
			for(int j=0; j<i; j++){
				printf("%d", steps[j].size());
				for(auto &k : steps[j]) printf(" %d %d", k.first, k.second);
				puts("");
			}
			return 0;
		}
	}
}

Submission Info

Submission Time
Task D - Distributed Sorting
User koosaga
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1486 Byte
Status WA
Exec Time 47 ms
Memory 3960 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:58:33: 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", steps[j].size());
                                 ^
./Main.cpp:32:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:34: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
AC × 2
WA × 1
AC × 17
WA × 14
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 256 KB
hand_02.txt AC 1 ms 256 KB
hand_03.txt AC 1 ms 256 KB
hand_04.txt AC 1 ms 256 KB
hand_05.txt WA 1 ms 256 KB
hand_06.txt WA 38 ms 3500 KB
hand_07.txt AC 32 ms 2552 KB
hand_08.txt AC 32 ms 2552 KB
random_01.txt WA 47 ms 3788 KB
random_02.txt WA 47 ms 3872 KB
sample-01.txt WA 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB
sorted_01.txt AC 31 ms 1528 KB
three_01.txt WA 25 ms 1528 KB
three_02.txt WA 28 ms 1528 KB
three_03.txt WA 38 ms 2040 KB
three_04.txt WA 44 ms 2804 KB
three_05.txt WA 44 ms 2804 KB
trans_01.txt AC 29 ms 1528 KB
trans_02.txt AC 26 ms 1528 KB
trans_03.txt AC 27 ms 1528 KB
trans_04.txt AC 28 ms 1528 KB
trans_05.txt AC 35 ms 1784 KB
trans_06.txt AC 43 ms 2552 KB
two_01.txt WA 45 ms 3960 KB
two_02.txt WA 45 ms 3960 KB
two_03.txt WA 44 ms 3960 KB