Submission #1440951


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]);
		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;
			if(chain.size()%2 == 0){
				for(int j=0; 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]]);
				}
			}else{
				int mid;
				if(chain.size()%4 == 1) mid = (chain.size()-1)/2;
				else mid = (chain.size()+1)/2;
				for(int j=0; j+1<mid; j+=2){
					print[ans].pb(chain[j]);
					print[ans].pb(chain[j+1]);
					swap(a[chain[j]],a[chain[j+1]]);
				}
				print[ans].pb(chain[mid]);
				print[ans].pb(chain.back());
				swap(a[chain[mid]],a[chain.back()]);
				for(int j=mid+1; j+1<chain.size()-1; 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++;
	}
	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
Task D - Distributed Sorting
User suhgyuho
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1989 Byte
Status WA
Exec Time 97 ms
Memory 5876 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:78: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
AC × 2
WA × 1
AC × 18
WA × 13
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 86 ms 5744 KB
hand_07.txt AC 34 ms 4600 KB
hand_08.txt AC 34 ms 4600 KB
random_01.txt WA 97 ms 5708 KB
random_02.txt WA 89 ms 5616 KB
sample-01.txt WA 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 3704 KB
three_01.txt WA 30 ms 3576 KB
three_02.txt WA 30 ms 3576 KB
three_03.txt WA 39 ms 4216 KB
three_04.txt WA 58 ms 5876 KB
three_05.txt WA 59 ms 5876 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 27 ms 3576 KB
trans_05.txt AC 30 ms 3832 KB
trans_06.txt AC 45 ms 4600 KB
two_01.txt WA 91 ms 5552 KB
two_02.txt WA 87 ms 5512 KB
two_03.txt WA 91 ms 5624 KB