Submission #208094

#	Time	Username	Problem	Language	Result	Execution time	Memory
208094		dOAOb	Lutrija (COCI19_lutrija)	C++14	14 / 70	798 ms	504 KiB

lutrija

#include<iostream>
#include<vector>
#include<queue>
#include<tuple>
#include<map>
#include<set>
using namespace std;

#define int long long

#ifdef lioraju
	#define ndbg(x) 
#else
	#define ndbg(x) x
#endif

typedef tuple<int, int> p2i;

signed main()
{
	ndbg( ios::sync_with_stdio(0); cin.tie(0); );
	auto checkPrime = [](int n)
	{
		for (int i=2;i*i<=n;i++)
			if (n%i==0) return 0;
		return 1;
	};
	
	map<int, int> vfr;
	int st, ed; cin>>st>>ed;
	if (st>ed) swap(st, ed);
	
	queue<p2i> qu; qu.push(p2i{st, -1});
	auto qu_push = [&](int np, int p)
	{
		if (np<2 || vfr.count(np) || !checkPrime(np))
			return;
		
		vfr[np]=-1, qu.push(p2i{np, p});
	};
	
	while (qu.size())
	{
		int p, fr; tie(p, fr) = qu.front(); qu.pop();
		vfr[p] = fr;
		
		if (p==ed)
		{
			int now = p;
			vector<int> v;
			while (now!=-1)
			{
				v.push_back(now);
				now = vfr[now];
			}
			
			cout<<v.size()<<'\n';
			for (int x: v) cout<<x<<' ';
			cout<<'\n';
			return 0;
		}
		
		if (!vfr.count(2) && checkPrime(p-2))
			vfr[2]=-1, qu.push(p2i{2, p});
		
		if (p!=2)
		{
			for (int vi=-2;vi<=2;vi+=4)
			{
				int np = p+vi;
				qu_push(np, p);
			}
		}
		else
		{
			for (int vi=-10;vi<=10;vi+=2)
			{
				if (checkPrime(st+vi-2)) qu_push(st+vi, p);
				if (checkPrime(ed+vi-2)) qu_push(ed+vi, p);
			}
		}
	}
	
	cout<<"-1\n";
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 7
• Subtask 5: 7 / 7
• Subtask 6: 0 / 7
• Subtask 7: 0 / 7
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7