TrickmanOff

Untitled

Aug 4th, 2019
301
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.50 KB | None | 0 0
  1. const int MAXN = 200000;
  2.  
  3. int n;
  4. int nums[MAXN];
  5. u_set<int> nums_set;
  6.  
  7. void input() {
  8.     cin >> n;
  9.     for (int i = 0; i < 2 * n; i++) {
  10.         cin >> nums[i];
  11.         nums_set.insert(nums[i]);
  12.     }
  13.    
  14.     sort(nums, nums + 2 * n);
  15. }
  16.  
  17. void part_case() {
  18.     int prev = 0;
  19.     for(int i = 0; i < 2*n; i++) {
  20.         prev = i;
  21.        
  22.         while(i+1 < 2*n && nums[i+1] == nums[i])
  23.             i++;
  24.        
  25.         int cur = i - prev + 1;
  26.         if(cur >= n) {
  27.             cout << nums[i] << ' ' << 0;
  28.             exit(0);
  29.         }
  30.     }
  31. }
  32.  
  33. void check(int pos, int d) {
  34.     int got = 1;
  35.     int prev = nums[pos];
  36.    
  37.     int a = prev + d;
  38.    
  39.     while(nums_set.count(a)) {
  40.         if(got == n)
  41.             break;
  42.         got++;
  43.         a += d;
  44.     }
  45.    
  46.     a = prev - d;
  47.    
  48.     while(nums_set.count(a)) {
  49.         if(got == n)
  50.             break;
  51.         got++;
  52.         a -= d;
  53.     }
  54.    
  55.     if (got >= n) {
  56.         cout << a+d << ' ' << d;
  57.         exit(0);
  58.     }
  59. }
  60.  
  61. void gen_div(int a, int pos) {
  62.     for (int d = 1; d * d <= a; d++) {
  63.         if (a % d == 0) {
  64.             check(pos, d);
  65.             check(pos, a / d);
  66.         }
  67.     }
  68. }
  69.  
  70. int main()
  71. {
  72.     input();
  73.     part_case();
  74.     srand(time(0));
  75.    
  76.     int TRIES = 10000;
  77.    
  78.     while (TRIES--) {
  79.         int a = rand() % (2 * n);
  80.         int b = rand() % (2 * n);
  81.        
  82.         if (b > a)
  83.             swap(a, b);
  84.        
  85.         gen_div(nums[a] - nums[b], b);
  86.     }
  87. }
Advertisement
Add Comment
Please, Sign In to add comment