oj.uz

Submission #344550

# Submission time Handle Problem Language Result Execution time Memory
344550 2021-01-06T05:39:40 Z limabeans Lutrija (COCI19_lutrija) C++17
0 / 70
 173 ms 492 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;



bool isprime(ll x) {
    for (ll i=2; i*i<=x; i++) {
	if (x%i==0) return false;
    }
    return true;
}



void solve(ll a, ll b, bool rev=false) {
    map<ll,ll> par;
    par[a] = -1;
	
    queue<ll> qq;
    qq.push(a);
    while (qq.size()) {
	ll at = qq.front();
	qq.pop();
	if (isprime(abs(at-b))) {
	    par[b] = at;
	    break;
	}
	for (ll dx: {-2,2}) {
	    ll to = dx+at;
	    if (par.count(to)) continue;
	    if (to>1 && isprime(to)) {
		par[to] = at;
		qq.push(to);
	    }
	}
	
    }

    if (!par.count(b)) {
	return;
    }

    vector<ll> path;
    while (b != a) {
	path.push_back(b);
	b = par[b];
    }

    path.push_back(b);

    if (rev) reverse(path.begin(), path.end());

    cout<<path.size()<<"\n";
    while (path.size()) {
	cout<<path.back()<<" ";
	path.pop_back();
    }
    cout<<endl;
    exit(0);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);


    assert(isprime(41));

    ll a,b;
    cin>>a>>b;

    if (isprime(abs(a-b))) {
	cout<<"2\n";
	cout<<a<<" "<<b<<"\n";
	exit(0);
    }

    solve(a,b);
    solve(b,a,true);

    out(-1);


    
    
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 7.0

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

Subtask #6
0 / 7.0

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

Subtask #7
0 / 7.0

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

Subtask #8
0 / 7.0

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

Subtask #9
0 / 7.0

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

Subtask #10
0 / 7.0

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