Submission #20233

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
20233	2016-06-17T05:21:38 Z	khuder	Sorting (IOI15_sorting)	C++	Compilation error	0 ms	0 KB

sorting

#include <iostream>
#include <cstdio>
#include "sorting.h"

using namespace std;

int n, m;
int s[200001], x[300001], y[300001], bob[200001], ax[300001], ay[300001], pos[200001];
int p[300001], q[300001], ansR;

void readData(){
	scanf("%d", &n);
	int i;
	for(i=0;i<n;i++){
		scanf("%d", &s[i]);
		bob[i]=s[i];
	}
		
	scanf("%d", &m);
	for(i=0;i<m;i++){
		scanf("%d%d", &x[i], &y[i]);
	}
}

void initBob(){
	for(int i=0;i<n;i++)
		bob[i]=s[i];	
}

void swap(int *a, int *b){
	int temp=*a;
	*a=*b;
	*b=temp;
}

void swapBob(int t){
	for(int i=0;i<t;i++){
		swap(&bob[x[i]], &bob[y[i]]);
	}
}

void printA(int *arr){
	for(int i=0;i<n;i++)
		cout << arr[i] << " ";
	cout << endl;
}

void doBob(int t){
	initBob();
	swapBob(t);
}

int swapCount(){
	int sC=0;
	
 	for(int i=0;i<n;i++){
		while(bob[i]!=i){
	
			ax[sC]=bob[bob[i]]; ay[sC]=bob[i];
	
			sC++;
			
			swap(&bob[bob[i]], &bob[i]);
		}
	}
	return sC;
}

int findPos(int number){
	for(int i=0;i<n;i++){
		if(number==s[i]){
			return i;
		}
	}	
}

void insertSwaps(int t, int ss){
	int i;
	for(i=0;i<n;i++){
		pos[s[i]]=i;
	}

	for(i=0;i<t;i++){
		
		swap(&s[x[i]], &s[y[i]]);
		swap(&pos[s[x[i]]], &pos[s[y[i]]]);
		
		if(i<ss){
			int a=pos[ax[i]], b=pos[ay[i]];

			//printf("%d %d\n", a, b);
            p[i]=a; q[i]=b;
 
			swap(&s[a], &s[b]);
			swap(&pos[s[a]], &pos[s[b]]);
			
		}
		else printf("0 0");
	}
}

void solve(){
	int l=0, r=n-1, sC, mid;
	while(l<r){
		mid=(l+r)/2;
		doBob(mid);
		sC=swapCount();
		if(sC<=mid){
			r=mid;
		}
		else l=mid+1;
	}
	ansR=r;
	doBob(r);
	sC=swapCount();
	insertSwaps(r, sC);
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n = N, s = S, x = X, y = Y, p = P, q = Q;
    solve();
    return ansR;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:120:16: error: incompatible types in assignment of 'int*' to 'int [200001]'
     n = N, s = S, x = X, y = Y, p = P, q = Q;
                ^
sorting.cpp:120:23: error: incompatible types in assignment of 'int*' to 'int [300001]'
     n = N, s = S, x = X, y = Y, p = P, q = Q;
                       ^
sorting.cpp:120:30: error: incompatible types in assignment of 'int*' to 'int [300001]'
     n = N, s = S, x = X, y = Y, p = P, q = Q;
                              ^
sorting.cpp:120:37: error: incompatible types in assignment of 'int*' to 'int [300001]'
     n = N, s = S, x = X, y = Y, p = P, q = Q;
                                     ^
sorting.cpp:120:44: error: incompatible types in assignment of 'int*' to 'int [300001]'
     n = N, s = S, x = X, y = Y, p = P, q = Q;
                                            ^
sorting.cpp:119:39: warning: unused parameter 'M' [-Wunused-parameter]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
                                       ^
sorting.cpp: In function 'void readData()':
sorting.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
sorting.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &s[i]);
   ~~~~~^~~~~~~~~~~~~
sorting.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
sorting.cpp:21: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: In function 'int findPos(int)':
sorting.cpp:75:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^