oj.uz

Submission #209324

# Submission time Handle Problem Language Result Execution time Memory
209324 2020-03-13T19:59:05 Z papa Lutrija (COCI19_lutrija) C++14
70 / 70
 405 ms 504 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
7.0 / 7.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 376 KB Output is correct
2 Correct 199 ms 376 KB Output is correct
3 Correct 405 ms 504 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 376 KB Output is correct
2 Correct 207 ms 384 KB Output is correct
3 Correct 285 ms 376 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 376 KB Output is correct
2 Correct 190 ms 504 KB Output is correct
3 Correct 263 ms 376 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 376 KB Output is correct
2 Correct 145 ms 504 KB Output is correct
3 Correct 96 ms 376 KB Output is correct