제출 #1264152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264152		goulthen	Lutrija (COCI19_lutrija)	C++20	70 / 70	57 ms	328 KiB

lutrija

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,a,b) for (int i = a; i <= b; ++i)
#define pb push_back

const int MAXN = 1e5 + 10;
map<int, vector<int>> g;
map<int, bool> mk;

bool prime(int x) {
	if (x%2 == 0 && x!=2) return 0;
	for (int i = 3; i*i <= x; i++) if (x%i==0) return 0;
	return 1;
}

void dfs(int u, vector<int> &ans, int tg) {
	mk[u] = 1;
	ans.pb(u);
	if (u==tg) return;
	for (int &v : g[u]) {
		if (mk[v]) continue;
		dfs(v,ans,tg);
	}
	if (ans.back() == tg) return;
	ans.pop_back();
}

int32_t main() {
	ios_base::sync_with_stdio(0);cin.tie(nullptr);
	int a,b;cin >> a >> b;

	if (prime(a+2)) {
		g[a].pb(a+2), g[a+2].pb(a);
		g[a+2].pb(2), g[2].pb(a+2);
	}

	if (prime(a-2)) {
		g[a].pb(a-2), g[a-2].pb(a);
		g[a].pb(2), g[2].pb(a);
	}

	if (prime(b+2)) {
		g[b].pb(b+2), g[b+2].pb(b);
		g[b+2].pb(2), g[2].pb(b+2);
	}

	if (prime(b-2)) {
		g[b].pb(b-2), g[b-2].pb(b);
		g[b].pb(2), g[2].pb(b);
	}


	vector<int> ans;
	dfs(a,ans, b);
	if (ans.back() != b) {
		cout << "-1\n";
		return 0;
	}
	cout << ans.size() << '\n';
	for (int &v : ans) cout << v << ' ';
	cout << '\n';

	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