oj.uz

Submission #223892

# Submission time Handle Problem Language Result Execution time Memory
223892 2020-04-16T19:58:57 Z penguinhacker Lutrija (COCI19_lutrija) C++14
70 / 70
 700 ms 504 KB 
//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

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.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
7.0 / 7.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 648 ms 388 KB Output is correct
2 Correct 433 ms 380 KB Output is correct
3 Correct 591 ms 384 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 504 KB Output is correct
2 Correct 398 ms 504 KB Output is correct
3 Correct 426 ms 384 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 504 KB Output is correct
2 Correct 436 ms 504 KB Output is correct
3 Correct 386 ms 384 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 504 KB Output is correct
2 Correct 315 ms 384 KB Output is correct
3 Correct 139 ms 384 KB Output is correct