oj.uz

Submission #1009452

# Submission time Handle Problem Language Result Execution time Memory
1009452 2024-06-27T14:19:02 Z bornag Experiments with Gorlum (IZhO13_expgorl) C++14
100 / 100
 2 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double

const ll inf = 0x3f3f3f3f3f3f3f3f;

ll tx, ty, lx, ly, gx, gy, k, si;
string s;

ld calc(ll xi, ll yi, ll xxi, ll yyi){
	return abs(xi-xxi)*abs(xi-xxi)+abs(yi-yyi)*abs(yi-yyi);
}

int main(){
	cin >> k >> s;
	
	cout << fixed << setprecision(12);
	si = s.size();
	
	for(auto x : s){
		if(x == 'L') tx--;
		else if(x == 'R') tx++;
		else if(x == 'F') ty++;
		else if(x == 'B') ty--;
	}
	
	cin >> lx >> ly >> gx >> gy;
	
	ld mni = calc(gx, gy, lx, ly);
	ld mxi = max(calc(gx, gy, lx, ly), calc(lx, ly, gx+tx*(k-1), gy+ty*(k-1)));
	for(int i = 0; i < si; i++){
		ll lo = 0;
		ll hi = k-1; // jer provjeravam i mid+1
		
		ll mid = (lo+hi)/2;
		
		while(lo < hi){
			mid = (lo+hi)/2;
			
			ld xc = gx + tx*mid; //nakon mid*s
			ld yc = gy + ty*mid; //nakon mid*s
			ld xd = gx + tx*(mid+1); //jos jedan dalje
			ld yd = gy + ty*(mid+1);
			
			if(calc(lx, ly, xc, yc) < calc(lx, ly, xd, yd)){
				hi = mid;
			} else {
				lo = mid+1;
			}
		}
		
		mid = (lo+hi)/2;
		
		mxi = max(mxi, max(calc(gx, gy, lx, ly), calc(lx, ly, gx+tx*(k-1), gy+ty*(k-1))));
		mni = min(mni, calc(lx, ly, gx + tx*mid, gy+ty*mid));
		
		char so = s[i];	
		if(so == 'L') gx--;
		else if(so == 'R') gx++;
		else if(so == 'F') gy++;
		else if(so == 'B') gy--;
	}
	
	cout << sqrt(mni) << ' ' << sqrt(mxi);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 2 ms 348 KB Output is correct