Submission #65562

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
65562	2018-08-08T04:20:56 Z	tugushka	Sorting (IOI15_sorting)	C++14	Compilation error	0 ms	0 KB

sorting

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#define M 600001
using namespace std;

int n, m, a[200002];
int x[M], y[M], p[M], q[M], tmp[M];
int p1[M];

void print(){
	for(int i = 0 ; i < n ; i++)
		cout << tmp[i] << ' ';
	cout << endl;
	
	for(int i = 0 ; i < n ; i++)
		cout << p1[i] << ' ';
	cout << endl;
	
}

bool check( int k ){
	for(int i = 0 ; i < n ; i++)
		tmp[i] = a[i];
	
	for(int i = 0 ; i < k ; i++)
		swap( tmp[ x[i] ], tmp[ y[i] ] );
	
	// p1[i] -> i-r toonii bairlal
	 
	for(int i = 0 ; i < n ; i++)
		p1[ tmp[i] ] = i;
	
//	cout << k << endl;
//	print();
//	cout << "----------------\n";
	
	int now = 0;
	for(int i = 0 ; i < n ; i++){
		if( now+1 > k ) break;

		if( tmp[i] == i ) continue;
		int f = p1[i];
		p[now] = i;
		q[now] = f;
		p1[ tmp[i] ] = f;
		p1[ i ] = i;
		swap( tmp[i], tmp[f] );
		now++;
//		cout << f << ' ' << i << endl;
//		print();
//		cout << "****************\n";
	}
	
//	print();
		
	for(int i = 0 ; i < n ; i++)
		if( tmp[i] != i ) return 0;
	
	while( now < k ) p[now] = q[now] = 0, now++;
	
	return 1;
}

int main()
{
//	freopen("sorting.in","r", stdin);
//	freopen("out.txt","w",stdout);
	scanf("%d", &n);
	for(int i = 0 ; i < n ; i++)
		scanf("%d", &a[i]);
	scanf("%d", &m);
	for(int i = 0 ; i < m ; i++)
		scanf("%d %d", &x[i], &y[i]);
	/*
	int res;
	for(int i = 0 ; i <= m ; i++)
		if( check(i) ){
			res = i;
			break;
		}
	*/
	int l = 0, r = m, res;
	while( l < r ){
		int mid = (l+r) / 2;
		bool f = check( mid );
//		cout << "END : " << f << endl;
//		cout << "#################\n";
		if( f ) r = mid, res = mid;
		else l = mid+1;
	}
	check( res );
	printf("%d\n", res);
	for(int i = 0 ; i < res ; i++)
		printf("%d %d\n", p[i], q[i]);
	
}

Compilation message

sorting.cpp: In function 'int main()':
sorting.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
sorting.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
sorting.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
sorting.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x[i], &y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sorting.cpp:85:20: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int l = 0, r = m, res;
                    ^~~
/tmp/ccEvoD5P.o: In function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'
/tmp/cctYopeB.o:sorting.cpp:(.text.startup+0x0): first defined here
/tmp/ccEvoD5P.o: In function `main':
grader.c:(.text.startup+0x517): undefined reference to `findSwapPairs(int, int*, int, int*, int*, int*, int*)'
collect2: error: ld returned 1 exit status