oj.uz

Submission #445075

# Submission time Handle Problem Language Result Execution time Memory
445075 2021-07-16T11:08:30 Z Tahmid690 Lutrija (COCI19_lutrija) C++14
70 / 70
 1249 ms 332 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;
vll vv,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){
	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;
}


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

void solve(){
	
	cin >> a >> b;
	
	
	bool xoxo=dfs(a,1,0);
	
	if(xoxo==0){
		cld.clear();
		xoxo=sd(a,1,0);
		if(xoxo==0){
			cout << -1 << endl;
			return;
		}
		ll yy=a;
		while(1){
			v.pb(yy);
			if(yy==2) break;
			yy=cld[yy];
		}
		cld.clear();
		xoxo=sd(b,v.size(),0);
		yy=b;
		
		if(xoxo==0){
			cout << -1 << endl;
			return;
		}
		
		while(1){
			if(yy==2) break;
			vv.pb(yy);
			yy=cld[yy];
		}
		reverse(all(vv));
		for(auto u:vv) v.pb(u);
		cout << v.size() << endl;
		for(auto u:v) cout << u << " ";
		return;
		
	}
	
	ll xx=a;
	while(1){
		v.pb(xx);
		if(xx==b) break;
		xx=cld[xx];
	}
	
	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:162:13: warning: unused variable 'cs' [-Wunused-variable]
  162 |     int T=1,cs=0;
      |             ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1070 ms 288 KB Output is correct
2 Correct 259 ms 304 KB Output is correct
3 Correct 96 ms 292 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1098 ms 292 KB Output is correct
2 Correct 92 ms 292 KB Output is correct
3 Correct 70 ms 288 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1249 ms 300 KB Output is correct
2 Correct 437 ms 204 KB Output is correct
3 Correct 65 ms 292 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1085 ms 292 KB Output is correct
2 Correct 197 ms 288 KB Output is correct
3 Correct 24 ms 204 KB Output is correct