oj.uz

Submission #116668

# Submission time Handle Problem Language Result Execution time Memory
116668 2019-06-13T13:32:30 Z emilem Board (CEOI13_board) C++14
40 / 100
 10 ms 640 KB 
#include <cassert>
#include <algorithm>
#include <iostream>
#include <string>
using std::swap;

long long Depth(const std::string& a)
{
	int depth = 0;
	for (auto dir = a.begin(); dir != a.end(); ++dir)
		if (*dir == 'U')
			--depth;
		else if (*dir == '1' || *dir == '2')
			++depth;
	assert(depth >= 0);
	return depth;
}
long long Coord(const std::string& a)
{
	long long coord = 0;
	for (auto dir = a.begin(); dir != a.end(); ++dir)
		switch (*dir)
		{
		case '1':
			coord *= 2; break;
		case '2':
			coord *= 2;
			++coord; break;
		case 'L':
			--coord; break;
		case 'R':
			++coord; break;
		case 'U':
			coord /= 2;
		}
	return coord;
}
int main()
{
	std::string path;
	std::cin >> path;
	long long aDepth = Depth(path);
	long long aCoord = Coord(path);
	std::cin >> path;
	long long bDepth = Depth(path);
	long long bCoord = Coord(path);
	if (aDepth > bDepth)
	{
		swap(aDepth, bDepth);
		swap(aCoord, bCoord);
	}
	long long depthSteps = bDepth - aDepth;
	while (bDepth > aDepth)
	{
		bCoord /= 2;
		--bDepth;
	}
	long long ans = depthSteps + std::abs(aCoord - bCoord);
	while (--aDepth && --bDepth)
	{
		depthSteps += 2;
		aCoord /= 2; bCoord /= 2;
		ans = std::min(ans, depthSteps + std::abs(aCoord - bCoord));
	}
	std::cout << ans << std::endl;

	char I;
	std::cin >> I;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 7 ms 512 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 10 ms 640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -