Submission #208097

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

lutrija

#include<iostream>
#include<algorithm>
#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)
	{
		if (n<0) n = -n;
		if (n<2) return 0;
		
		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;
	
	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];
			}
			reverse(v.begin(), v.end());
			
			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-p)) qu_push(st+vi, p);
				if (checkPrime(ed+vi-p)) qu_push(ed+vi, p);
			}
		}
	}
	
	cout<<"-1\n";
}

Compilation message (stderr)

lutrija.cpp: In function 'int main()':
lutrija.cpp:62:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for (int x: v) cout<<x<<' '; cout<<'\n';
    ^~~
lutrija.cpp:62:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for (int x: v) cout<<x<<' '; cout<<'\n';
                                 ^~~~

• 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