Submission #1440982


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]);
		//a[i] = i-1; if(a[i] == 0) a[i] = N;
		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;

			x = -1;
            for(int j=0; j+3<chain.size(); j+=4){
                print[ans].pb(chain[j+1]);
                print[ans].pb(chain[j+2]);
                swap(a[chain[j+1]],a[chain[j+2]]);
                print[ans].pb(chain[j+3]);
                print[ans].pb(chain[j]);
                swap(a[chain[j+3]],a[chain[j]]);
                x = j+3;
            }
            x++;
            for(int j=x; 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]]);
			}
		}
		if(print[ans].size() == 0) break;
		ans++;
	}
	for(int i=1; i<=N; i++){
		if(i != a[i]) while(true);
	}
	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 1969 Byte
Status WA
Exec Time 87 ms
Memory 5616 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:75: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 × 3
AC × 25
WA × 6
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 79 ms 5616 KB
hand_07.txt AC 34 ms 4600 KB
hand_08.txt AC 34 ms 4600 KB
random_01.txt WA 84 ms 5580 KB
random_02.txt WA 87 ms 5616 KB
sample-01.txt AC 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 3576 KB
three_01.txt AC 30 ms 3576 KB
three_02.txt AC 30 ms 3576 KB
three_03.txt AC 38 ms 3960 KB
three_04.txt AC 53 ms 4856 KB
three_05.txt AC 53 ms 4856 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 26 ms 3576 KB
trans_05.txt AC 31 ms 3832 KB
trans_06.txt AC 46 ms 4600 KB
two_01.txt WA 82 ms 5500 KB
two_02.txt WA 82 ms 5480 KB
two_03.txt WA 82 ms 5460 KB