Submission #223892

#	Time	Username	Problem	Language	Result	Execution time	Memory
223892		penguinhacker	Lutrija (COCI19_lutrija)	C++14	70 / 70	700 ms	504 KiB

lutrija

//TASK: Lutrija

#include <bits/stdc++.h>
using namespace std;

#define ll long long

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

ll A, B, diff;
vector<ll> nodes;
map<pair<ll, ll>, bool> adj;

vector<ll> path;
void dfs(ll u) {
	path.push_back(u);
	if (u==B) {
		cout << path.size() << '\n';
		for (int i=0; i<path.size(); ++i) {
			cout << path[i] << (i<path.size()-1?' ':'\n');
		}
		exit(0);
	}
	for (int i=0; i<nodes.size(); ++i) {
		if (adj[make_pair(u, nodes[i])]&&find(path.begin(), path.end(), nodes[i])==path.end()) {
			dfs(nodes[i]);
		}
	}
	path.pop_back();
}

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

	cin >> A >> B;

	set<ll> temp;
	temp.insert(2);
	for (int i=-1; i<=1; ++i) {
		if (check(A+2*i))
			temp.insert(A+2*i);
		if (check(B+2*i))
			temp.insert(B+2*i);
	}
	for (const ll &i : temp)
		nodes.push_back(i);
	int n = nodes.size();
	for (int i=0; i<n; ++i) {
		for (int j=0; j<n; ++j) {
			adj[make_pair(nodes[i], nodes[j])] = 0;
			if (check(abs(nodes[i]-nodes[j]))) {
				adj[make_pair(nodes[i], nodes[j])] = 1;
			}
		}	
	}
	dfs(A);
	cout << -1 << '\n';
	return 0;
}

Compilation message (stderr)

lutrija.cpp: In function 'void dfs(long long int)':
lutrija.cpp:27:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<path.size(); ++i) {
                 ~^~~~~~~~~~~~
lutrija.cpp:28:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    cout << path[i] << (i<path.size()-1?' ':'\n');
                        ~^~~~~~~~~~~~~~
lutrija.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<nodes.size(); ++i) {
                ~^~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7