Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- #include <cstdlib>
- #include <algorithm>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <climits>
- #include <string>
- #include <set>
- #include <cmath>
- #include <map>
- #include <unordered_map>
- #include <numeric>
- #include <random>
- #include <memory>
- #include <chrono>
- #include <iterator>
- #include <functional>
- #include <unordered_set>
- #include <cassert>
- #include <cstring>
- #ifdef LOCAL
- #include "debug.h"
- #else
- #define debug(x...)
- #endif
- /*
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("O3")
- #pragma GCC optimize("unroll-loops")
- */
- //#define int ll
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef pair < int, int > pii;
- typedef pair < ll, ll > pll;
- #define sz(x) int((x).size())
- #ifndef LOCAL
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- #else
- mt19937 rng(228);
- #endif
- const int N = 2e2 + 7;
- const int inf = INT_MAX / 2;
- const ll INF = LLONG_MAX / 3;
- const int MOD = 1e9 + 7;
- const double eps = 1e-6;
- const string cars[] = {"🚗", "🚕", "🚙"};
- const int N1 = 1e5 + 2;
- short cnt[N1];
- vector < int > a;
- short n;
- char state[N][N1];
- bool solve(int x, int d, short k) {
- if (state[k][d] != '0') {
- return state[k][d] - '1';
- }
- if (k == n) {
- state[k][d] = '1';
- return false;
- }
- else {
- short j = 0;
- if (cnt[d]) {
- j = cnt[d];
- }
- else {
- for (int y : a) {
- j += (abs(x - y) % d == 0);
- }
- cnt[d] = j;
- }
- bool res = false;
- if (j > k) {
- res |= !solve(x, d, k + 1);
- }
- for (int y : a) {
- if (x == y) {
- continue;
- }
- int g = __gcd(abs(x - y), d);
- if (g != 1 && g != d) {
- res |= !solve(x, g, k + 1);
- }
- }
- state[k][d] = '1' + res;
- return res;
- }
- }
- vector < int > solve1() {
- vector < int > ans;
- for (short i = 0; i < n; i++) {
- bool res = false;
- memset(cnt, 0, sizeof cnt);
- memset(state, '0', sizeof state);
- for (short j = 0; j < n; j++) {
- if (i == j) {
- continue;
- }
- if (abs(a[i] - a[j]) > 1) {
- res |= !solve(a[i], abs(a[i] - a[j]), 2);
- }
- }
- if (res ^ 1) {
- ans.push_back(a[i]);
- }
- }
- return ans;
- }
- signed main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- cout << fixed << setprecision(4);
- ios::sync_with_stdio(false);
- cin.tie();
- cout.tie();
- cin >> n;
- a = vector < int > (n);
- for (int& x : a) {
- cin >> x;
- }
- auto ans = solve1();
- cout << sz(ans) << "\n";
- for (int x : ans) {
- cout << x << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement