Advertisement
gt22

Untitled

Jul 16th, 2020
802
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.38 KB | None | 0 0
  1.  
  2. #include <vector>
  3. #include "optimization.h"
  4. #include <unordered_map>
  5. using namespace std;
  6. #define N 100001
  7. int n;
  8. unordered_map<int, int> am;
  9. int as[2 * N];
  10.  
  11. int a = 43215, b = 54321;
  12. unsigned int cur = 0;
  13. inline unsigned int nextRand24() {
  14.     cur = cur * a + b;
  15.     return cur >> 8u;
  16. }
  17.  
  18. int check(int a0, int d) {
  19.     if(d == 0) return INT_MAX;
  20.     int count = 1;
  21.     int base = a0;
  22.     int ax = a0 - d;
  23.     while(am[ax]) {
  24.         count++;
  25.         base = ax;
  26.         ax -= d;
  27.     }
  28.     ax = a0 + d;
  29.     while(am[ax]) {
  30.         count++;
  31.         ax += d;
  32.     }
  33.     return count >= n ? base : INT_MAX;
  34. }
  35.  
  36. int main() {
  37.     n = readInt();
  38.     int size = 2 * n;
  39.     int maxCount = 0;
  40.     int maxCountElem = -1;
  41.     for (int i = 0; i < size; ++i) {
  42.         int x = readInt();
  43.         as[i] = x;
  44.         int count = ++am[x];
  45.         if(count > maxCount) {
  46.             maxCount = count;
  47.             maxCountElem = x;
  48.         }
  49.     }
  50.     if(maxCount > n) {
  51.         writeInt(maxCountElem, ' ');
  52.         writeInt(0, '\n');
  53.     } else {
  54.         int base, d;
  55.         do {
  56.             int a1 = as[nextRand24() % size];
  57.             int a2 = as[nextRand24() % size];
  58.             if(a1 > a2) swap(a1, a2);
  59.             base = check(a1, d = a2 - a1);
  60.         } while(base == INT_MAX);
  61.         writeInt(base, ' ');
  62.         writeInt(d, '\n');
  63.     }
  64.     return 0;
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement