oj.uz

Submission #1029323

# Submission time Handle Problem Language Result Execution time Memory
1029323 2024-07-20T16:26:21 Z 0pt1mus23 Lutrija (COCI19_lutrija) C++14
70 / 70
 614 ms 436 KB 
#pragma GCC optimize("O3", "inline")
#define skillissue <bits/stdc++.h>
#define ultra_mal std
#include skillissue
using namespace ultra_mal;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define endl '\n' 
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()
#define hash FhashF
const int mod = 1e9 +7, sze = 1E3 +100, inf = LLONG_MAX, P = 1453;
// const int L = 30;

int prime(int aa){
    if(aa<2){
        return 0;
    }
    for(int i = 2;i*i<=aa;i++){
        if(aa%i==0){
            return 0;        
        }
    }

    return 1;
}

map<int,vector<int>> graph;

int x,y;
map<int,int> used;
void dfs(int node,vector<int> path){
    path.pb(node);
    used[node]=1;
    if(node==y){
        cout<<path.size()<<endl;
        for(auto v:path){
            cout<<v<<" ";
        }
        cout<<endl;
        exit(0);
    }
    for(auto v:graph[node]){
        if(!used[v]){
            dfs(v,path);
        }
    }
}

void cave(){
    cin>>x>>y;
    vector<int> lst={x+2,x-2,y-2,y+2,x,y,2};
    for(auto v:lst){
        if(prime(v)){
            for(auto xx:lst){
                if(prime(xx)){
                    if(prime(abs(xx-v))){
                        graph[v].pb(xx);
                    }
                }
            }
        }
    }
    vector<int> path;
    dfs(x,path);
    drop(-1);

    
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    // cin>>tt;
    
    while(tt--){
        cave();
    }

    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 432 KB Output is correct
2 Correct 313 ms 432 KB Output is correct
3 Correct 614 ms 348 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 344 KB Output is correct
2 Correct 279 ms 348 KB Output is correct
3 Correct 454 ms 348 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 344 KB Output is correct
2 Correct 318 ms 348 KB Output is correct
3 Correct 417 ms 348 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 348 KB Output is correct
2 Correct 236 ms 348 KB Output is correct
3 Correct 152 ms 436 KB Output is correct