Cod sursa(job #814759)

Utilizator cornel92Radu Cornel cornel92 Data 15 noiembrie 2012 23:53:16
Problema Subsir crescator maximal Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.27 kb
#include<stdio.h>
#include<stdlib.h>

int n;
int *seifs;
int lastLocked = 1;
int existBetter( int thiefIndex, int *targets, int *distances){
	int i;
	int c = 0;
	for(i = lastLocked; i < targets[thiefIndex]; i++){
        	if( seifs[i]  >= thiefIndex && distances[seifs[i]] < distances[thiefIndex])
			return 1;
        } 
       return 0;
}

chooseThieves(){
	int i;
	int  *targets, *distances;
	targets = malloc(sizeof(int) * (n+1));
	distances = malloc(sizeof(int) * (n+1));
	for(i = 1; i <= n;i++){
		targets[seifs[i]] = i;
		distances[seifs[i]] = seifs[i] > i?seifs[i] - i:i-seifs[i];
    	}
    	for( i = 1; i <= n; i++ ){
             	if(targets[i] >= lastLocked && !existBetter( i, targets, distances)){
                        	lastLocked = targets[i] + 1;   
                        	printf("%d ", i);        
             	}             
    	}
}


int citeste(char *filename){
    freopen(filename, "r", stdin); 
    scanf("%d", &n);
    getchar();
    seifs = (int *)malloc(sizeof(int) * (n+1));
    int i;
    for(i = 1; i <= n; i++){
          scanf("%d", seifs+i);
          getchar();
    }
}

int main(int argc, char **argv){
    
    citeste(argv[1]);
    freopen(argv[2], "w", stdout);
    chooseThieves(); 
    return 0;   
}