oj.uz

Submission #208094

# Submission time Handle Problem Language Result Execution time Memory
208094 2020-03-10T02:39:14 Z dOAOb Lutrija (COCI19_lutrija) C++14
14 / 70
 798 ms 504 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
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

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

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 376 KB Output is correct

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 741 ms 416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 715 ms 388 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Incorrect 75 ms 376 KB Output isn't correct

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 798 ms 388 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Incorrect 70 ms 376 KB Output isn't correct

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 504 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Incorrect 28 ms 376 KB Output isn't correct