oj.uz

Submission #208097

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

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.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 376 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 380 KB Output is correct
4 Correct 5 ms 376 KB Output is correct

Subtask #3
7.0 / 7.0

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

Subtask #4
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 #5
7.0 / 7.0

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

Subtask #6
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 #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 744 ms 504 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 103 ms 376 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 504 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 75 ms 376 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 781 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 70 ms 376 KB Output is correct

Subtask #10
7.0 / 7.0

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