Submission #209324

#	Time	Username	Problem	Language	Result	Execution time	Memory
209324		papa	Lutrija (COCI19_lutrija)	C++14	70 / 70	405 ms	504 KiB

lutrija

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a,b;
vector<int> adj[10];
vector<ll> svi;
vector<ll> filt;
int pre[10];
int vis[10];

//bfs resenje

bool bfs()
{
    vis[0] = 1;
    queue<int> q;
    q.push(0);

    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        for(int s : adj[x])
        {
            if(!vis[s])
            {
                pre[s] = x;
                vis[s] = 1;
                q.push(s);
            }
        }
    }

    if(vis[filt.size()-1]) return true;

    return false;
}

bool prime(ll x)
{
    if(x==0) return false;
    if(x==1) return false;
    if(x==2) return true;

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

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

   cin >> a >> b;

   svi.push_back(a-2);
   svi.push_back(a+2);
   svi.push_back(2);
   svi.push_back(b-2);
   svi.push_back(b+2);

   filt.push_back(a);

   for(int i=0;i<svi.size();i++) if(prime(svi[i])) filt.push_back(svi[i]);

   filt.push_back(b);

   for(int i=0;i<filt.size()-1;i++)
   {
       for(int j=i+1;j<filt.size();j++)
       {
           if(prime(abs(filt[i]-filt[j])))
           {
               adj[i].push_back(j);
               adj[j].push_back(i);
           }
       }
   }

   if(bfs())
   {
       int x = filt.size()-1;
       stack<ll> st;
       while(x > 0)
       {
          st.push(filt[x]);
          x = pre[x];
       }

       cout << st.size() + 1 << "\n";
       cout << a << " ";
       while(!st.empty())
       {
           cout << st.top() << " ";
           st.pop();
       }
   }
   else cout << -1;

   return 0;
}

Compilation message (stderr)

lutrija.cpp: In function 'int main()':
lutrija.cpp:69:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<svi.size();i++) if(prime(svi[i])) filt.push_back(svi[i]);
                ~^~~~~~~~~~~
lutrija.cpp:73:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<filt.size()-1;i++)
                ~^~~~~~~~~~~~~~
lutrija.cpp:75:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(int j=i+1;j<filt.size();j++)
                      ~^~~~~~~~~~~~

• 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