oj.uz

Submission #223882

# Submission time Handle Problem Language Result Execution time Memory
223882 2020-04-16T19:47:58 Z penguinhacker Lutrija (COCI19_lutrija) C++14
42 / 70
 348 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<int> nodes;
map<pair<int, int>, bool> adj;

vector<int> path;
void dfs(int 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<int> 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 int &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(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 4 ms 384 KB Output is correct
2 Correct 4 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 6 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 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 5 ms 384 KB Output is correct

Subtask #6
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 #7
0 / 7.0

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

Subtask #8
0 / 7.0

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

Subtask #9
0 / 7.0

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

Subtask #10
0 / 7.0

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