Submission #493625

#	Time	Username	Problem	Language	Result	Execution time	Memory
493625		inksamurai	Lutrija (COCI19_lutrija)	C++17	70 / 70	630 ms	324 KiB

lutrija

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3dDwnkq ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;

ll prime(ll c){
	if(c==2) return true;
	if(c<=1) return false;
	for(ll j=2;j<=sqrt(c);j++) 
		if(c%j==0) return false;
	return true;
}

int main(){
_3dDwnkq;
	ll a,b;
	cin>>a>>b;
	vec(ll) xs;
	for(ll j=-4;j<=4;j++) if(prime(a+j)) xs.pb(a+j);
	for(ll j=-4;j<=4;j++) if(prime(b+j)) xs.pb(b+j);
	xs.pb(2);
	std::map<ll,ll> mp;
	auto bfs=[&](){	
		mp[a]=-1;
		queue<ll> que;
		que.push(a);
		while(sz(que)){
			ll top=que.front();
			que.pop();
			for(auto x : xs){
				if(x!=top and prime(abs(x-top))){
					if(mp.find(x)==mp.end()){
						mp[x]=top;
						que.push(x);
					}
				}
			}
		}
	};
	bfs();
	vec(ll) pans;
	while(true){
		pans.pb(b);
		if(mp.find(b)==mp.end()){
			cout<<"-1\n";
			exit(0);
		}
		if(mp[b]==-1) break;
		b=mp[b];
	}
	reverse(all(pans));
	cout<<sz(pans)<<"\n";
	for(auto x : pans) cout<<x<<" ";
//	
	return 0;
}

• 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