Submission #1090517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090517		Vkrisztian01	Lutrija (COCI19_lutrija)	C++14	70 / 70	133 ms	436 KiB

lutrija

#include <iostream>
#include<bits/stdc++.h>
typedef long long ll;

using namespace std;

bool is_prime(ll a) {

    if( a == 0 || a == 1) return false;

    ll k = sqrt(a);
    for(ll i = 2; i <= k; i++)
        if(a % i == 0) return false;
    return true;
}

void dfs(int v,vector<vector<int> > &adj,vector<int> &origin) {

    for(int to : adj[v]) {

        if(origin[to] ==-1) {

            origin[to] = v;
            dfs(to,adj,origin);

        }

    }


}

int main()
{
    ll a, b;
    cin >> a >> b;

    if(a == b) {

        cout << 1 << "\n";
        cout << a;
        return 0;

    }

    vector<ll> v = {a,2,a - 2,a + 2,b - 2,b + 2,b};

    for(int i = 0; i < v.size(); i++)
        if(!is_prime(v[i])) {v.erase(v.begin() + i); --i;}

    int n = v.size();

    vector<vector<int> > adj(n);

    for(int i = 0; i < n; i++) {

        for(int j = i + 1; j < n; j++) {

            if(is_prime(abs(v[i] - v[j])))
            {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }

        }
    }

    vector<int> origin(n, -1);
    origin[0] = -2;
    dfs(0,adj,origin);

    if(origin[n - 1] == -1)
    {
        cout<<-1;
        return 0;
    }

    vector<ll> ans;
    int k = n-1;

    while(k != -2)
    {
        ans.push_back(v[k]);
        k = origin[k];
    }

    reverse(ans.begin(),ans.end());

    cout<<ans.size()<<"\n";

    for(ll x : ans) cout<<x<<" ";

    return 0;
}

Compilation message (stderr)

lutrija.cpp: In function 'int main()':
lutrija.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i = 0; i < v.size(); i++)
      |                    ~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7