Submission #89105

#	Time	Username	Problem	Language	Result	Execution time	Memory
89105		nika	Experiments with Gorlum (IZhO13_expgorl)	C++14	100 / 100	213 ms	2172 KiB

expgorl

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define lo long long 
#define inf 2005000000
#define md 1000000007
#define pb push_back
#define li 10005
#define li2 100005
#define ii pair<int,int>
using namespace std;
int k,gx,gy,lx,ly,n,px,py,vismin[li2],vismax[li2];
char s[li];
vector< pair<int,int> > po;
double amin=inf,amax=-inf;
double cal(ii a,ii b){
	return sqrt(1ll*(a.fi-b.fi)*(a.fi-b.fi)+1ll*(a.se-b.se)*(a.se-b.se));
}
int denemin(){
	double dist=inf;
	int res;
	for(int i=0;i<(int)po.size();i++){
		if(vismin[i]==1) continue;
		if(dist>cal(po[i],mp(lx,ly))){
			dist=cal(po[i],mp(lx,ly));
			res=i;
		}
	}
	return res;
}
int denemax(){
	double dist=-inf;
	int res;
	for(int i=0;i<(int)po.size();i++){
		if(vismax[i]==1) continue;
		if(dist<cal(po[i],mp(lx,ly))){
			dist=cal(po[i],mp(lx,ly));
			res=i;
		}
	}
	return res;
}
void trymin(int x){
	ii cur=po[x];
	amin=min(amin,cal(cur,mp(lx,ly)));
	for(int i=1;i<=n;i++){
		if(s[i]=='L') cur.fi--;
		if(s[i]=='R') cur.fi++;
		if(s[i]=='F') cur.se++;
		if(s[i]=='B') cur.se--;
		amin=min(amin,cal(cur,mp(lx,ly)));
	}
}
void trymax(int x){
	ii cur=po[x];
	amax=max(amax,cal(cur,mp(lx,ly)));
	for(int i=1;i<=n;i++){
		if(s[i]=='L') cur.fi--;
		if(s[i]=='R') cur.fi++;
		if(s[i]=='F') cur.se++;
		if(s[i]=='B') cur.se--;
		amax=max(amax,cal(cur,mp(lx,ly)));
	}
}
int main(){
	scanf("%d",&k);
	scanf("%s",s+1);
	n=strlen(s+1);
	scanf("%d %d %d %d",&lx,&ly,&gx,&gy);
	for(int i=1;i<=n;i++){
		if(s[i]=='L') px--;
		if(s[i]=='R') px++;
		if(s[i]=='F') py++;
		if(s[i]=='B') py--;
	}
	po.pb(mp(gx,gy));
	for(int i=1;i<k;i++){
		po.pb(mp(po.back().fi+px,po.back().se+py));
	}
	int magic=min(k,100);
	for(int i=1;i<=magic;i++){
		int pmin=denemin();
		int pmax=denemax();
		trymin(pmin);
		trymax(pmax);
		vismin[pmin]=1;
		vismax[pmax]=1;
	}
	printf("%.12lf %.12lf\n",amin,amax);
	return 0;
}

Compilation message (stderr)

expgorl.cpp: In function 'int main()':
expgorl.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&k);
  ~~~~~^~~~~~~~~
expgorl.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s+1);
  ~~~~~^~~~~~~~~~
expgorl.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d",&lx,&ly,&gx,&gy);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
expgorl.cpp: In function 'int denemin()':
expgorl.cpp:30:9: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return res;
         ^~~
expgorl.cpp: In function 'int denemax()':
expgorl.cpp:42:9: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return res;
         ^~~

• Subtask 1: 100 / 100