Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- const int MAXN = 200000;
- int n;
- int nums[MAXN];
- u_set<int> nums_set;
- void input() {
- cin >> n;
- for (int i = 0; i < 2 * n; i++) {
- cin >> nums[i];
- nums_set.insert(nums[i]);
- }
- sort(nums, nums + 2 * n);
- }
- void part_case() {
- int prev = 0;
- for(int i = 0; i < 2*n; i++) {
- prev = i;
- while(i+1 < 2*n && nums[i+1] == nums[i])
- i++;
- int cur = i - prev + 1;
- if(cur >= n) {
- cout << nums[i] << ' ' << 0;
- exit(0);
- }
- }
- }
- void check(int pos, int d) {
- int got = 1;
- int prev = nums[pos];
- int a = prev + d;
- while(nums_set.count(a)) {
- if(got == n)
- break;
- got++;
- a += d;
- }
- a = prev - d;
- while(nums_set.count(a)) {
- if(got == n)
- break;
- got++;
- a -= d;
- }
- if (got >= n) {
- cout << a+d << ' ' << d;
- exit(0);
- }
- }
- void gen_div(int a, int pos) {
- for (int d = 1; d * d <= a; d++) {
- if (a % d == 0) {
- check(pos, d);
- check(pos, a / d);
- }
- }
- }
- int main()
- {
- input();
- part_case();
- srand(time(0));
- int TRIES = 10000;
- while (TRIES--) {
- int a = rand() % (2 * n);
- int b = rand() % (2 * n);
- if (b > a)
- swap(a, b);
- gen_div(nums[a] - nums[b], b);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement