Advertisement
aayyk

Untitled

Dec 18th, 2019
208
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.87 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <queue>
  7. #include <stack>
  8. #include <climits>
  9. #include <string>
  10. #include <set>
  11. #include <cmath>
  12. #include <map>
  13. #include <unordered_map>
  14. #include <numeric>
  15. #include <random>
  16. #include <memory>
  17. #include <chrono>
  18. #include <iterator>
  19. #include <functional>
  20. #include <unordered_set>
  21. #include <cassert>
  22. #include <cstring>
  23. #ifdef LOCAL
  24. #include "debug.h"
  25. #else
  26. #define debug(x...)
  27. #endif
  28. /*
  29. #pragma GCC optimize("Ofast")
  30. #pragma GCC optimize("O3")
  31. #pragma GCC optimize("unroll-loops")
  32. */
  33. //#define int ll
  34.  
  35.  
  36.  
  37. using namespace std;
  38. typedef long long ll;
  39. typedef long double ld;
  40. typedef pair < int, int > pii;
  41. typedef pair < ll, ll > pll;
  42. #define sz(x) int((x).size())
  43.  
  44. #ifndef LOCAL
  45. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  46. #else
  47. mt19937 rng(228);
  48. #endif
  49.  
  50. const int N = 2e2 + 7;
  51. const int inf = INT_MAX / 2;
  52. const ll INF = LLONG_MAX / 3;
  53. const int MOD = 1e9 + 7;
  54. const double eps = 1e-6;
  55. const string cars[] = {"🚗", "🚕", "🚙"};
  56.  
  57. vector < int > a;
  58. short n;
  59.  
  60. unordered_map < int, bool > state[N];
  61.  
  62. bool solve(int x, int d, short k) {
  63.     if (state[k].find(d) != state[k].end()) {
  64.         return state[k][d];
  65.     }
  66.  
  67.     if (k == n) {
  68.         state[k][d] = false;
  69.         return false;
  70.     }
  71.     else {
  72.         short j = 0;
  73.         for (int y : a) {
  74.             j += (abs(x - y) % d == 0);
  75.         }
  76.  
  77.         bool res = false;    
  78.    
  79.         if (j > k) {
  80.             res |= !solve(x, d, k + 1);
  81.         }
  82.  
  83.         for (int y : a) {
  84.             if (x == y) {
  85.                 continue;
  86.             }
  87.  
  88.             int g = __gcd(abs(x - y), d);
  89.             if (g != 1 && g != d) {
  90.                 res |= !solve(x, g, k + 1);
  91.             }
  92.         }
  93.  
  94.         state[k][d] = res;
  95.         return res;
  96.     }
  97. }
  98.  
  99. vector < int > solve1() {
  100.     vector < int > ans;
  101.     for (short i = 0; i < n; i++) {
  102.         bool res = false;
  103.         for (int k = 0; k < N; k++) {
  104.             state[k].clear();
  105.         }
  106.  
  107.         for (short j = 0; j < n; j++) {
  108.             if (i == j) {
  109.                 continue;
  110.             }
  111.  
  112.             if (abs(a[i] - a[j]) > 1) {
  113.                 res |= !solve(a[i], abs(a[i] - a[j]), 2);
  114.             }
  115.         }
  116.  
  117.         if (res ^ 1) {
  118.             ans.push_back(a[i]);
  119.         }
  120.     }
  121.     return ans;
  122. }
  123.  
  124.  
  125. signed main() {
  126. #ifdef LOCAL
  127.     freopen("input.txt", "r", stdin);
  128.     freopen("output.txt", "w", stdout);
  129. #endif
  130.     cout << fixed << setprecision(4);
  131.     ios::sync_with_stdio(false);
  132.     cin.tie();
  133.     cout.tie();
  134.  
  135.     cin >> n;
  136.    
  137.     a = vector < int > (n);
  138.  
  139.     for (int& x : a) {
  140.         cin >> x;
  141.     }
  142.  
  143.     auto ans = solve1();
  144.  
  145.     cout << sz(ans) << "\n";
  146.     for (int x : ans) {
  147.         cout << x << " ";
  148.     }
  149.  
  150.     return 0;
  151. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement