oj.uz

Submission #205344

# Submission time Handle Problem Language Result Execution time Memory
205344 2020-02-28T15:28:50 Z mraron Lutrija (COCI19_lutrija) C++14
70 / 70
 536 ms 388 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool ip(ll x) {
	if(x<=1) return false;
	for(ll i=2;i*i<=x;++i) {
		if(x%i==0) return false;
	}
	return true;
}
int main() {
	ll a,b;
	cin>>a>>b;
	vector<ll> lst;
	lst.push_back(a);
	lst.push_back(b);
	lst.push_back(2);
	if(ip(a-2)) lst.push_back(a-2);	
	if(ip(a+2)) lst.push_back(a+2);
	if(ip(b-2)) lst.push_back(b-2);	
	if(ip(b+2)) lst.push_back(b+2);
	map<ll,ll> par;
	par[a]=0;
	queue<ll> q;
	q.push(a);
	while(!q.empty()) {
		ll fr=q.front();
		q.pop();
		//cerr<<fr<<"\n";
		for(auto i:lst) {
			if(ip(abs(fr-i)) && par.count(i)==0) {
				par[i]=fr;
				q.push(i);
			}
		}
	}
	
	if(par.count(b)!=0) {
		vector<ll> ans;
		while(b>0) {
			ans.push_back(b);
			b=par[b];
		}
		reverse(ans.begin(),ans.end());
		cout<<ans.size()<<"\n";
		for(auto i:ans) cout<<i<<" ";
		cout<<"\n";
	}else cout<<"-1\n";
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
7.0 / 7.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 356 KB Output is correct
2 Correct 102 ms 256 KB Output is correct
3 Correct 494 ms 376 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 376 KB Output is correct
2 Correct 100 ms 256 KB Output is correct
3 Correct 360 ms 256 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 388 KB Output is correct
2 Correct 95 ms 256 KB Output is correct
3 Correct 330 ms 376 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 376 KB Output is correct
2 Correct 76 ms 364 KB Output is correct
3 Correct 120 ms 376 KB Output is correct