Spioni

[•Mitza444]

Buna am si eu o problema de pe .campion si nush de ce imi pica la ultimu test la timpu de executie.... .....chiar nu stiu ce sa  mai  fac.......Ma puteti ajuta? http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=573

Cod:

#include<cstdio>
using namespace std;
int x[1001],y[1001],s[1001];
int main(){
	int n,xa=0,ya=0,k,i,j,gasit=0;
	char c;
	FILE * pFile;
	pFile=fopen("spioni.in","r");
	fscanf(pFile,"%d",&n);
	for(i=1;i<=n;i++){
		fscanf(pFile,"%d",&x[i]);
		fscanf(pFile,"%d",&y[i]);
	}
	for(j=1;j<=n;j++){
			if((x[j]==xa && y[j]==ya) || (x[j]==xa-1 && y[j]==ya-1) || (x[j]==xa && y[j]==ya-1) || (x[j]==xa+1 && y[j]==ya-1) || (x[j]==xa-1 && y[j]==ya) || (x[j]==xa+1 && y[j]==ya) || (x[j]==xa-1 && y[j]==ya+1) || (x[j]==xa && y[j]==ya+1) || (x[j]==xa+1 && y[j]==ya+1)){
				s[j]=1;gasit=1;}
		}
	fscanf(pFile,"%d",&k);
	for(i=1;i<=k+1;i++){
		fscanf(pFile,"%c",&c);
		switch(c){
		case 'N':ya++;break;
		case 'S':ya--;break;
		case 'V':xa--;break;
		case 'E':xa++;break;
		}
		for(j=1;j<=n;j++){
			if((x[j]==xa && y[j]==ya) || (x[j]==xa-1 && y[j]==ya-1) || (x[j]==xa && y[j]==ya-1) || (x[j]==xa+1 && y[j]==ya-1) || (x[j]==xa-1 && y[j]==ya) || (x[j]==xa+1 && y[j]==ya) || (x[j]==xa-1 && y[j]==ya+1) || (x[j]==xa && y[j]==ya+1) || (x[j]==xa+1 && y[j]==ya+1)){
				s[j]=1;gasit=1;}
		}
	}
	pFile=fopen("spioni.out","w");
	if(!gasit)fprintf(pFile,"-1");
	else {
	for(i=1;i<=n;i++){
		if(s[i])fprintf(pFile,"%d\n",i);
	}
	}
	return 0;
}

[•scipianus]

N-am apucat inca sa ma uit atent pe problema si pe sursa ta,dar din ce am zarit asa "dubios" in sursa, te-as sfatui sa incerci pe moment sa refaci portiunea unde ai folosit switch,intrucat contine 4 break-uri care in general sunt mari consumatoare de timp   Incearca cu if 

[•Mitza444]

Am incercat si cu if poate ca e un pic mai rapid,dar tot nu este de ajuns ca sa treaca testul

[•Mitza444]

Ma mai puteti ajuta cu ceva idei?? chiar nu stiu ce sa-i mai fac sa treaca la timpul de executie............

[•klamathix]

Pai ai O( n * k ), e prea mult. Fa o cautare binara or something, nu mai verifica toti spionii la fiecare pas.

[•Mitza444]

ok,o sa vad si ideea ta desi e cam greu pt. ca trebuie sa verific de fiecare data ca sa  nu pierd solutii...dar am auzit ca este o modalitate de citire mai rapida ceva cu parsare,dar nu stiu cum sa fac:|

[•Mitza444]

Am incercat sa mai pun niste conditii ca sa nu verifice toti spionii,dar nu merge:| cred ca trebuie facut ceva la citire ca sa merga mai repede,dar nu stiu ce mai aveti ceva idei??ca la ultimul test trebuie citit 1000 de spioni + 100000 caractere

[•crushack]

Da poti sa reduci complexitatea la O(n+k), daca ti o matrice [0..N-1][0..N-1] si in fiecare celula ti 0 daca nu e nici un spion acolo sau numarul spionului daca e. Apoi la fiecare pas verifici daca in vre-o casuta alaturata , sau chiar pe casuta curenta e vre-un spion si adaugi daca e cazul

Sper ca te ajuta

Da, n-am vazut dimensiunile, merge daca faci cautare binara

[•Mitza444]

Buna am refacut problema.De data asta am facut os tructura de date in care am retinut toti spionii si dupaia am retinut toate punctele in care poate fi un spion si apoi vectorul acela care are toate punctele unde poate fi un spion l-am sortat si dupaia fac o cautare binara ca sa intersectez cei 2 vectori,dar nu stiu de ce cautarea mea binara nu functioneaza corect........
Ma puteti ajuta??

Cod:

#include<cstdio>
#include<algorithm>
using namespace std;
int m,i;
char c[100001];
struct spion{
	int x,y;
}a[1001],b[800001];
inline bool compare( const spion& p1, const spion& p2 )
{
       return p1.x == p2.x ? p1.y < p2.y : p1.x < p2.x;
}

int caut (int s, int d)
{
    if(s>d)
        return -1;
    else
        {
            m =(s+d)/2;
            if (a[i].x==b[m].x){
				if(a[i].y==b[m].y)return 1;
				if(a[i].y<b[i].y)return caut(s,m-1);
				if(a[i].y>b[i].y)return caut(m+1,d);
			}
            if (a[i].x<b[m].x){
                return caut(s,m-1);}
            if(a[i].x>b[m].x){
                return caut(m+1,d);}
        }
}
int main(){
	int n,k,s=-1,j,xa=0,ya=0,gasit=0;
	int dx[]={-1,0,1,-1,0,1,-1,0,1}, dy[]={-1,-1,-1,0,0,0,1,1,1};
	FILE * pFile;
	pFile=fopen("spioni.in","r");
	fscanf(pFile,"%d",&n);
	for(i=0;i<n;i++){
		fscanf(pFile,"%d%d",&a[i].x,&a[i].y);
	}
	fscanf(pFile,"%d",&k);
	fscanf(pFile,"%s",&c);
	for(j=0;j<9;j++){
			s++;
			b[s].x=xa+dx[j];
			b[s].y=ya+dy[j];
		}
	for(i=0;i<k;i++){
		if(c[i]=='N')ya++;
		if(c[i]=='S')ya--;
		if(c[i]=='V')xa--;
		if(c[i]=='E')xa++;
		for(j=0;j<9;j++){
			s++;
			b[s].x=xa+dx[j];
			b[s].y=ya+dy[j];
		}
	}
	sort( b, b+s+1, compare );
	pFile=fopen("spioni.out","w");
	for(i=0;i<n;i++){
		if(caut(1,s)==1){fprintf(pFile,"%d\n",i+1);gasit=1;}
	}
	if(!gasit)fprintf(pFile,"-1");
	
	return 0;
}

[•crushack]

Ok , mi se pare foarte dubios cum faci cautarea binara, in primul rand functiei tale trebuie sa-i dai un spion pe care sa-l cauti.
Antetul trebuie sa fie ceva de genu :

Cod:

int caut(int s,int d,spion spy);

si ca sa nu mai pui atatea if-uri poti sa folosesti functia de comparare pe care ai facut-o

sper ca te ajuta