Advertisement
TrickmanOff

Untitled

Aug 4th, 2019
277
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.02 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <iostream>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <functional>
  7. #include <bitset>
  8. #include <string>
  9. #include <stack>
  10. #include <time.h>
  11. #include <unordered_set>
  12. using namespace std;
  13.  
  14. #define ll long long
  15. #define cin in
  16. #define cout out
  17. #define pii pair<int, int>
  18. #define ld long double
  19. #define u_set unordered_set
  20.  
  21. //ifstream in("input.txt");
  22. //ofstream out("output.txt");
  23.  
  24. ifstream in("arithm.in");
  25. ofstream out("arithm.out");
  26.  
  27. const int MAXN = 200000;
  28.  
  29. int n;
  30. int nums[MAXN];
  31. u_set<int> nums_set;
  32.  
  33. void input() {
  34.     cin >> n;
  35.     for (int i = 0; i < 2 * n; i++) {
  36.         cin >> nums[i];
  37.         nums_set.insert(nums[i]);
  38.     }
  39.    
  40.     sort(nums, nums + 2 * n);
  41. }
  42.  
  43. void part_case() {
  44.     int prev = 0;
  45.     for(int i = 0; i < 2*n; i++) {
  46.         while(i+1 < 2*n && nums[i+1] == nums[i])
  47.             i++;
  48.        
  49.         int cur = i - prev + 1;
  50.         if(cur >= n) {
  51.             cout << nums[i] << ' ' << 0;
  52.             exit(0);
  53.         }
  54.        
  55.         prev = i+1;
  56.     }
  57. }
  58.  
  59. void check(int pos, int d) {
  60.     if(d == 0) return;
  61.    
  62.     int got = 1;
  63.     int prev = nums[pos];
  64.    
  65.     int a = prev + d;
  66.    
  67.     while(nums_set.count(a)) {
  68.         got++;
  69.         a += d;
  70.     }
  71.    
  72.     a = prev - d;
  73.    
  74.     while(nums_set.count(a)) {
  75.         got++;
  76.         a -= d;
  77.     }
  78.    
  79.     if (got >= n) {
  80.         cout << a+d << ' ' << d;
  81.         exit(0);
  82.     }
  83. }
  84.  
  85. void gen_div(int a, int pos) {
  86.     if (a == 0) {
  87.         check(pos, 0);
  88.         return;
  89.     }
  90.    
  91.     for (int d = 1; d * d <= a; d++) {
  92.         if (a % d == 0) {
  93.             check(pos, d);
  94.             check(pos, a / d);
  95.         }
  96.     }
  97. }
  98.  
  99. int main()
  100. {
  101.     input();
  102.     part_case();
  103.     srand(time(0));
  104.    
  105.     int TRIES = 20000;
  106.    
  107.     while (TRIES--) {
  108.         int a = rand() % (2 * n);
  109.         int b = rand() % (2 * n);
  110.        
  111.         if (b > a)
  112.             swap(a, b);
  113.        
  114.         gen_div(nums[a] - nums[b], b);
  115.     }
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement