oj.uz

답안 #493625

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
493625 2021-12-12T12:05:25 Z inksamurai Lutrija (COCI19_lutrija) C++17
70 / 70
 630 ms 324 KB 
#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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #4
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #6
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #7
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 609 ms 288 KB Output is correct
2 Correct 297 ms 324 KB Output is correct
3 Correct 626 ms 296 KB Output is correct

Subtask #8
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 587 ms 288 KB Output is correct
2 Correct 193 ms 312 KB Output is correct
3 Correct 447 ms 204 KB Output is correct

Subtask #9
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 630 ms 288 KB Output is correct
2 Correct 226 ms 296 KB Output is correct
3 Correct 420 ms 304 KB Output is correct

Subtask #10
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 477 ms 292 KB Output is correct
2 Correct 154 ms 296 KB Output is correct
3 Correct 148 ms 292 KB Output is correct