oj.uz

Submission #1089601

# Submission time Handle Problem Language Result Execution time Memory
1089601 2024-09-16T19:16:32 Z Gervid Lutrija (COCI19_lutrija) C++17
70 / 70
 201 ms 460 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <limits.h>
#include <algorithm>
#include <math.h>

using namespace std;

set<long long> been;
vector<long long> out;

bool isprime(long long n)
{
	for (long long i = 2LL; i*i <= n; i++)
	{
		if (n % i == 0) return false;
	}
	return true;
}

bool dfs(long long node, long long goal)
{
	if (node == goal)
	{
		out.push_back(node);
		return true;
	}

	for (long long neighbour : {2LL, node + 2LL, node - 2LL > 2LL ? node - 2LL : 4LL})
	{
		if (!been.count(neighbour) && isprime(neighbour) && isprime(abs(node - neighbour)))
		{
			been.insert(neighbour);
			if (dfs(neighbour, goal))
			{
				out.push_back(node);
				return true;
			}
		}
	}
	return false;
}

int main()
{
	iostream::sync_with_stdio(0);
	cin.tie(0);

	long long a, b;
	cin >> a >> b;

	if (!dfs(a, b))
	{//need to go down to 2, or not possible
		if (been.count(2))
		{
			been.clear();

			dfs(b, a);

			if (been.count(2))
			{
				out.clear();
				been.clear();
				dfs(a, 2);

				vector<long long> firsthalf;
				out.swap(firsthalf);

				been.clear();
				dfs(b, 2);

				cout << out.size() + firsthalf.size() - 1 << '\n';
				for (int i = firsthalf.size() - 1; i > 0; i--)
				{
					cout << firsthalf[i] << ' ';
				}
				for (int i = 0; i < out.size(); i++)
				{
					cout << out[i] << ' ';
				}
				return 0;
			}
		}

		cout << -1;
		return 0;
	}

	cout << out.size() << '\n';
	for (int i = out.size() - 1; i >= 0; i--)
	{
		cout << out[i] << ' ';
	}
}

Compilation message

lutrija.cpp: In function 'int main()':
lutrija.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i = 0; i < out.size(); i++)
      |                     ~~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 384 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 23 ms 348 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 17 ms 344 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 15 ms 344 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 432 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 6 ms 460 KB Output is correct