제출 #218267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
218267		vonatlus	Lutrija (COCI19_lutrija)	C++14	70 / 70	584 ms	504 KiB

lutrija

/// 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 / 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