Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<algorithm>
- #include<iostream>
- #include<iomanip>
- #include<stdio.h>
- #include<bitset>
- #include<vector>
- #include<string>
- #include<queue>
- #include<cmath>
- #include<ctime>
- #include<stack>
- #include<map>
- #include<set>
- #include<unordered_map>
- using namespace std;
- typedef long long LL;
- typedef long double LD;
- typedef pair<LL,LL> PLL;
- typedef pair<LD,LD> PDD;
- typedef pair<int,int> PII;
- typedef pair<PII,PII> PPII;
- #define PRINT(a) cerr<<#a<<" = "<<(a)<<'\n'
- #define B_E(a) a.begin(), a.end()
- #define PB push_back
- #define MP make_pair
- #define S second
- #define F first
- inline void file() {
- #ifdef _WIN32
- return;
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- if (0) {
- freopen(".in", "r", stdin);
- freopen(".out", "w", stdout);
- }
- }
- inline void read(LL& n) {
- #define nxt h = getchar_unlocked()
- #define nxt h = getchar()
- char h; n = 0;
- for (nxt; h<'0' || h>'9'; nxt);
- for (; h>='0' && h<='9'; nxt)
- n = n*10 + h-'0';
- #undef nxt
- }
- const LL INF = 2e9;
- vector<LL> a;
- map<LL,PLL> m;
- int n;
- /// O(n log n)
- inline void check(LL d) {
- m.clear();
- LL mx = 0;
- LL ost;
- for (LL i:a) {
- ost = (i+INF)%d;
- if ( m[ost].S ){
- LL x = i - m[ost].F;
- if ( !x ) continue;
- if ( x == d )
- ++m[ost].S;
- else
- m[ost].S = 1;
- } else
- m[ost].S = 1;
- m[ost].F = i;
- if ( m[ost].S >= n ) {
- cout<<i-d*(n-1)<<' '<<d<<endl;
- exit(0);
- }
- }
- }
- inline void alt_check(LL d) {
- vector<PLL> m(d);
- for (int i=0; i<d; ++i)
- m[i] = MP(0,0);
- LL mx = 0;
- LL ost;
- for (LL i:a) {
- ost = (i+INF)%d;
- if ( m[ost].S ){
- LL x = i - m[ost].F;
- if ( !x ) continue;
- if ( x == d )
- ++m[ost].S;
- else
- m[ost].S = 1;
- } else
- m[ost].S = 1;
- m[ost].F = i;
- if ( m[ost].S >= n ) {
- cout<<i-d*(n-1)<<' '<<d<<endl;
- exit(0);
- }
- }
- }
- inline void check_0() {
- if ( n == 1 ) {
- cout<<a[0]<<' '<<0<<endl;
- exit(0);
- }
- LL last,cnt;
- last = 1e9+1;
- cnt = 0;
- for (LL i:a)
- if ( i == last ) {
- if ( ++cnt >= n ) {
- cout<<i<<' '<<0<<endl;
- exit(0);
- }
- } else {
- last = i;
- cnt = 1;
- }
- }
- map<LL,int> sum;
- vector<PLL> v;
- main()
- { file();
- //freopen("kek321.txt", "r", stdin);
- LL x;
- read(x);
- n = x;
- a.resize(n*2);
- for (int i=0; i<n*2; ++i)
- read(a[i]);
- sort(B_E(a));
- check_0();
- ++sum[ a[1]-a[0] ];
- for (int i=2; i<n*2; ++i) {
- ++sum[ a[i]-a[i-1] ];
- ++sum[ a[i]-a[i-2] ];
- }
- sum.erase(0);
- for (PLL i:sum)
- v.PB( MP(-i.S, i.F) );
- sort(B_E(v));
- for (PLL i:v)
- if ( i.S > n*2 )
- check(i.S);
- else
- alt_check(i.S);
- cout<<"0 0"<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement