Pagini recente » Cod sursa (job #175538) | Cod sursa (job #646852) | Cod sursa (job #1818409) | Cod sursa (job #2938464) | Cod sursa (job #814764)
Cod sursa(job #814764)
#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("scmax.in");
freopen("scmax.out", "w", stdout);
chooseThieves();
return 0;
}