Submission #84454

# Submission time Handle Problem Language Result Execution time Memory
84454 2018-11-15T08:24:30 Z hamzqq9 Experiments with Gorlum (IZhO13_expgorl) C++14
0 / 100
1000 ms 1708 KB
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 2005000000
#define MOD 1000000007
#define N 300005
#define M 1000005
#define LOG 18
#define KOK 4000000
using namespace std;

int k,n,lx,ly,gx,gy,igmn[N],igmx[N];
double amin=inf,amax=-inf;
vector<ii> po;
char s[N];

double gds(ii x,ii y) {

	return sqrt(1ll*(x.st-y.st)*(x.st-y.st)+1ll*(x.nd-y.nd)*(x.nd-y.nd));

}

void try_max(int ind) {

	ii cur=po[ind];

	umax(amax,gds(cur,{lx,ly}));

	for(int i=1;i<=n;i++) {

		if(s[i]=='L') cur.st--;
		if(s[i]=='R') cur.st++;
		if(s[i]=='F') cur.nd++;
		if(s[i]=='B') cur.nd--;

		umax(amax,gds(cur,{lx,ly}));

	}

}

void try_min(int ind) {

	ii cur=po[ind];

	umin(amin,gds(cur,{lx,ly}));

	for(int i=1;i<=n;i++) {

		if(s[i]=='L') cur.st--;
		if(s[i]=='R') cur.st++;
		if(s[i]=='F') cur.nd++;
		if(s[i]=='B') cur.nd--;

		umin(amin,gds(cur,{lx,ly}));

	}

}

int fmax() {

	double dist=-inf;
	int ret;

	for(int i=0;i<sz(po);i++) {

		if(igmx[i]) continue ;

		double cur=gds(po[i],{lx,ly});

		if(dist<cur) {

			dist=cur;
			ret=i;

		} 

	}

	return ret;

}

int fmin() {

	double dist=inf;
	int ret;

	for(int i=0;i<sz(po);i++) {

		if(igmn[i]) continue ;

		double cur=gds(po[i],{lx,ly});

		if(dist>cur) {

			dist=cur;
			ret=i;

		} 

	}

	return ret;

}

int main() {

	//freopen("input.txt","r",stdin);

	scanf("%d",&k);

	scanf("%s",s+1);

	n=strlen(s+1);

	scanf("%d %d",&lx,&ly);
	scanf("%d %d",&gx,&gy);

	int px=0,py=0;

	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({gx,gy});

	for(int i=1;i<k;i++) {

		po.pb({po.back().st+px,po.back().nd+py});

	}

	int magic=min(k,k);

	for(int i=1;i<=magic;i++) {

		/*int pmin=fmin();
		int pmax=fmax();

		try_min(pmin);
		try_max(pmax);

		igmn[pmin]=1;
		igmx[pmax]=1;*/

		try_min(i-1);
		try_max(i-1);

	}

	printf("%.12lf %.12lf\n",amin,amax);

}

Compilation message

expgorl.cpp: In function 'int main()':
expgorl.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&k);
  ~~~~~^~~~~~~~~
expgorl.cpp:129:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s+1);
  ~~~~~^~~~~~~~~~
expgorl.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&lx,&ly);
  ~~~~~^~~~~~~~~~~~~~~~~
expgorl.cpp:134:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&gx,&gy);
  ~~~~~^~~~~~~~~~~~~~~~~
expgorl.cpp: In function 'int fmax()':
expgorl.cpp:95:9: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return ret;
         ^~~
expgorl.cpp: In function 'int fmin()':
expgorl.cpp:119:9: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return ret;
         ^~~
# Verdict Execution time Memory Grader output
1 Correct 419 ms 760 KB Output is correct
2 Correct 538 ms 760 KB Output is correct
3 Correct 592 ms 760 KB Output is correct
4 Correct 627 ms 788 KB Output is correct
5 Correct 323 ms 792 KB Output is correct
6 Correct 479 ms 936 KB Output is correct
7 Correct 534 ms 936 KB Output is correct
8 Correct 725 ms 948 KB Output is correct
9 Execution timed out 1085 ms 1708 KB Time limit exceeded
10 Halted 0 ms 0 KB -