oj.uz

Submission #217597

# Submission time Handle Problem Language Result Execution time Memory
217597 2020-03-30T10:31:26 Z bayemirov Lutrija (COCI19_lutrija) C++17
70 / 70
 771 ms 508 KB 
//bayemirov                                       
#include <bits/stdc++.h>               

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;

#define pb push_back

const ll INF = 1e9;
const int d[] = {0, 2, -2};

map<ll, ll> dist, p;
map<ll, vector<ll>> adj;
vector<ll> v = {2};
ll a, b;

bool isPrime(ll x) {
	if (x < 2) return 0;
	for (ll i = 2; i * i <= x; i++)
		if (x % i == 0)
			return 0;
	return 1;
}

void bfs() {
	for (auto x : v) dist[x] = INF;
	dist[a] = 0;
	queue<ll> q;
	q.push(a);
	while (!q.empty()) {
		ll v = q.front();
		q.pop();
		for (auto to : adj[v]) {
			if (dist[to] > dist[v] + 1) {
				dist[to] = dist[v] + 1;
				p[to] = v;
				q.push(to);
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> a >> b;
	for (int i = 0; i < 3; i++) {
		if (isPrime(a+d[i])) v.pb(a+d[i]);
		if (isPrime(b+d[i])) v.pb(b+d[i]);
	}
	for (int i = 0; i < v.size(); i++)
		for (int j = 0; j < v.size(); j++)
			if (isPrime(abs(v[i]-v[j])))
				adj[v[i]].pb(v[j]);
	bfs();
	if (dist[b] == INF) cout << -1, exit(0);
	p[a] = -1;
	vector<ll> ans;
	while (b != -1) {
		ans.pb(b);
		b = p[b];
	}
	reverse(ans.begin(), ans.end());
	cout << ans.size() << "\n";
	for (auto x : ans) cout << x << ' ';
	return 0;
}

Compilation message

lutrija.cpp: In function 'int main()':
lutrija.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++)
                  ~~^~~~~~~~~~
lutrija.cpp:55:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < v.size(); j++)
                   ~~^~~~~~~~~~

Subtask #1
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 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct

Subtask #2
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 4 ms 384 KB Output is correct
4 Correct 4 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 4 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 4 ms 384 KB Output is correct

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

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 384 KB Output is correct
2 Correct 429 ms 384 KB Output is correct
3 Correct 771 ms 396 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 624 ms 504 KB Output is correct
2 Correct 399 ms 384 KB Output is correct
3 Correct 561 ms 392 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 693 ms 508 KB Output is correct
2 Correct 445 ms 504 KB Output is correct
3 Correct 541 ms 384 KB Output is correct

Subtask #10
7.0 / 7.0

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