oj.uz

Submission #218267

# Submission time Handle Problem Language Result Execution time Memory
218267 2020-04-01T18:33:18 Z vonatlus Lutrija (COCI19_lutrija) C++14
70 / 70
 584 ms 504 KB 
/// wa ^3^

#pragma GCC optimize("O3")

#include<bits/stdc++.h>
                           
#define x first
#define y second
#define pb push_back
#define sz(x) (int) x.size()
 
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;

const int MOD = 1e9+7;
const int INF32 = 1e9 + 1e2;
                                                                   
void stndrtn() {
#ifdef accepted
    freopen(".in", "r", stdin);      
#endif        
}                                                         

const bool flag = 0;

bool prime(ll x) { 
    if (x < 2)
        return 0;
    for (int i = 2; i <= sqrt(x); ++i)
        if (x % i == 0)
            return 0;
    return 1;
}

int p[10];

bool was[10];

vector<int> adj[10];

void dfs(int x = 0) {
    was[x] = 1;
    for (int to : adj[x])
        if (!was[to])
            dfs(to), p[to] = x;
}

void maincode() {
    ll a, b;
    cin >> a >> b;
    vector<ll> v = {a, b, 2};
    for (int i = -1; i < 2; i += 2) {
        if (prime(a + 2*i))
            v.pb(a + 2*i);
        if (prime(b + 2*i))
            v.pb(b + 2*i);
    }
    for (int i = 0; i < sz(v); ++i)
        for (int j = 0; j < sz(v); ++j) 
            if (prime(abs(v[i]-v[j])))
                adj[i].pb(j);
    dfs();
    p[0] = 0;
    if (!was[1])
        cout << -1, exit(0);
    int cur = 1;
    vector<int> ans;
    while (cur) {
        ans.pb(cur);
        cur = p[cur];
    }
    reverse(ans.begin(), ans.end());
    cout << sz(ans)+1 << "\n" << a << " ";
    for (int x : ans)
        cout << v[x] << " ";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr), stndrtn();
    int ts = 1;
    if (flag) 
        cin >> ts;
    while (ts--)
        maincode(); 
    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
7.0 / 7.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 384 KB Output is correct
2 Correct 294 ms 384 KB Output is correct
3 Correct 584 ms 504 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 384 KB Output is correct
2 Correct 285 ms 384 KB Output is correct
3 Correct 423 ms 504 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 384 KB Output is correct
2 Correct 272 ms 384 KB Output is correct
3 Correct 384 ms 384 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 504 KB Output is correct
2 Correct 213 ms 384 KB Output is correct
3 Correct 140 ms 504 KB Output is correct