Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include "optimization.h"
- #include <unordered_map>
- using namespace std;
- #define N 100001
- int n;
- unordered_map<int, int> am;
- int as[2 * N];
- int a = 43215, b = 54321;
- unsigned int cur = 0;
- inline unsigned int nextRand24() {
- cur = cur * a + b;
- return cur >> 8u;
- }
- int check(int a0, int d) {
- if(d == 0) return INT_MAX;
- int count = 1;
- int base = a0;
- int ax = a0 - d;
- while(am[ax]) {
- count++;
- base = ax;
- ax -= d;
- }
- ax = a0 + d;
- while(am[ax]) {
- count++;
- ax += d;
- }
- return count >= n ? base : INT_MAX;
- }
- int main() {
- n = readInt();
- int size = 2 * n;
- int maxCount = 0;
- int maxCountElem = -1;
- for (int i = 0; i < size; ++i) {
- int x = readInt();
- as[i] = x;
- int count = ++am[x];
- if(count > maxCount) {
- maxCount = count;
- maxCountElem = x;
- }
- }
- if(maxCount > n) {
- writeInt(maxCountElem, ' ');
- writeInt(0, '\n');
- } else {
- int base, d;
- do {
- int a1 = as[nextRand24() % size];
- int a2 = as[nextRand24() % size];
- if(a1 > a2) swap(a1, a2);
- base = check(a1, d = a2 - a1);
- } while(base == INT_MAX);
- writeInt(base, ' ');
- writeInt(d, '\n');
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement