Advertisement
aayyk

Untitled

Dec 18th, 2019
170
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.01 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. const int N1 = 1e5 + 2;
  58.  
  59. short cnt[N1];
  60. vector < int > a;
  61. short n;
  62.  
  63. char state[N][N1];
  64.  
  65. bool solve(int x, int d, short k) {
  66.     if (state[k][d] != '0') {
  67.         return state[k][d] - '1';
  68.     }
  69.  
  70.     if (k == n) {
  71.         state[k][d] = '1';
  72.         return false;
  73.     }
  74.     else {
  75.         short j = 0;
  76.        
  77.         if (cnt[d]) {
  78.             j = cnt[d];
  79.         }
  80.         else {
  81.             for (int y : a) {
  82.                 j += (abs(x - y) % d == 0);
  83.             }
  84.             cnt[d] = j;
  85.         }
  86.  
  87.         bool res = false;    
  88.    
  89.         if (j > k) {
  90.             res |= !solve(x, d, k + 1);
  91.         }
  92.  
  93.         for (int y : a) {
  94.             if (x == y) {
  95.                 continue;
  96.             }
  97.  
  98.             int g = __gcd(abs(x - y), d);
  99.             if (g != 1 && g != d) {
  100.                 res |= !solve(x, g, k + 1);
  101.             }
  102.         }
  103.  
  104.         state[k][d] = '1' + res;
  105.         return res;
  106.     }
  107. }
  108.  
  109. vector < int > solve1() {
  110.     vector < int > ans;
  111.     for (short i = 0; i < n; i++) {
  112.         bool res = false;
  113.         memset(cnt, 0, sizeof cnt);
  114.         memset(state, '0', sizeof state);
  115.  
  116.         for (short j = 0; j < n; j++) {
  117.             if (i == j) {
  118.                 continue;
  119.             }
  120.  
  121.             if (abs(a[i] - a[j]) > 1) {
  122.                 res |= !solve(a[i], abs(a[i] - a[j]), 2);
  123.             }
  124.         }
  125.  
  126.         if (res ^ 1) {
  127.             ans.push_back(a[i]);
  128.         }
  129.     }
  130.     return ans;
  131. }
  132.  
  133.  
  134. signed main() {
  135. #ifdef LOCAL
  136.     freopen("input.txt", "r", stdin);
  137.     freopen("output.txt", "w", stdout);
  138. #endif
  139.     cout << fixed << setprecision(4);
  140.     ios::sync_with_stdio(false);
  141.     cin.tie();
  142.     cout.tie();
  143.  
  144.     cin >> n;
  145.    
  146.     a = vector < int > (n);
  147.  
  148.     for (int& x : a) {
  149.         cin >> x;
  150.     }
  151.  
  152.     auto ans = solve1();
  153.  
  154.     cout << sz(ans) << "\n";
  155.     for (int x : ans) {
  156.         cout << x << " ";
  157.     }
  158.  
  159.     return 0;
  160. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement