oj.uz

답안 #445058

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
445058 2021-07-16T10:37:47 Z Tahmid690 Lutrija (COCI19_lutrija) C++14
0 / 70
 570 ms 324 KB 
// "Say:He is the Most Merciful,We have believed in him and upon him we have relied" [67:29]
 
//#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx2")
//#pragma GCC optimize("unroll-loops")
 
#include<bits/stdc++.h>
using namespace std;
                                                     
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 */
 
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<ll> vll;
typedef vector<int> vii;
typedef map<int,int> mpi;
typedef map<ll,ll> mpl;
typedef unordered_map<int,int> umpi;
typedef unordered_map<ll,ll> umpl;
 
#define ump unordered_map
#define mod 1000000007
#define inf 1000000000000000006
#define infi 1000000009
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl '\n'
#define pi acos(-1.0)
#define dec(n) fixed << setprecision(n)
#define N 200005
//#define int long long

ll a,b,f;
vll v;
mpl cld;

bool isprime(ll m){
	
	bool cc=0;
	if(m<=1) return 0;
	for(ll i=2;i*i<=m;i++){
		if(m%i==0) cc=1;
	}
	return cc^1;
}

bool dfs(ll n,ll l,ll chk){
	//cout << n << endl;
	if(n>1000000000000000) return 0;
	if(l>30) return 0;
	if(n==b) return 1;
	bool x=0;
	if(isprime(n+2) && chk!=1){
		x=dfs(n+2,l+1,2);
		if(x==1) cld[n]=n+2;
		if(x==1) return 1;
	}
	if(isprime(n-2) && chk!=2){
		x=dfs(n-2,l+1,1);
		if(x==1) cld[n]=n-2;
		if(x==1) return 1;
	}
	if(isprime(n-2) && chk!=3){
		x=dfs(2,l+1,3);
		if(x==1) cld[n]=2;
		if(x==1) return 1;
	}
	return 0;
}

void solve(){
	cin >> a >> b;
	if(a==2) f=1;
	if(a==2) swap(a,b);
	bool xoxo=dfs(a,1,0);
	if(xoxo==0){
		cout << -1 << endl;
		return;
	}
	ll xx=a;
	while(1){
		v.pb(xx);
		if(xx==b) break;
		xx=cld[xx];
	}
	if(f) reverse(all(v));
	cout << v.size() << endl;
	for(auto u:v) cout << u << " ";
}

signed main(){
    fastio;
    //srand(chrono::steady_clock::now().time_since_epoch().count());
    int T=1,cs=0;
    //cin >> T;
    while(T--){
        //cout << "Case " << ++cs << ":" << " " ; 
    	solve();
    } 
}

Compilation message

lutrija.cpp: In function 'int main()':
lutrija.cpp:105:13: warning: unused variable 'cs' [-Wunused-variable]
  105 |     int T=1,cs=0;
      |             ^~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 440 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 476 ms 292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 569 ms 292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 570 ms 324 KB Output isn't correct
2 Halted 0 ms 0 KB -