Advertisement
Guest User

Untitled

a guest
Aug 16th, 2017
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.82 KB | None | 0 0
  1. #include<algorithm>
  2. #include<iostream>
  3. #include<iomanip>
  4. #include<stdio.h>
  5. #include<bitset>
  6. #include<vector>
  7. #include<string>
  8. #include<queue>
  9. #include<cmath>
  10. #include<ctime>
  11. #include<stack>
  12. #include<map>
  13. #include<set>
  14. #include<unordered_map>
  15. using namespace std;
  16. typedef long long LL;
  17. typedef long double LD;
  18. typedef pair<LL,LL> PLL;
  19. typedef pair<LD,LD> PDD;
  20. typedef pair<int,int> PII;
  21. typedef pair<PII,PII> PPII;
  22. #define PRINT(a) cerr<<#a<<" = "<<(a)<<'\n'
  23. #define B_E(a) a.begin(), a.end()
  24. #define PB push_back
  25. #define MP make_pair
  26. #define S second
  27. #define F first
  28. inline void file() {
  29.     #ifdef _WIN32
  30.         return;
  31.     #endif
  32.  
  33.     ios_base::sync_with_stdio(false);
  34.     cin.tie(NULL);
  35.     cout.tie(NULL);
  36.  
  37.     if (0) {
  38.         freopen(".in",  "r", stdin);
  39.         freopen(".out", "w", stdout);
  40.     }
  41. }
  42. inline void read(LL& n) {
  43.     #define nxt h = getchar_unlocked()
  44.     #define nxt h = getchar()
  45.     char h; n = 0;
  46.     for (nxt; h<'0' || h>'9'; nxt);
  47.     for (; h>='0' && h<='9'; nxt)
  48.         n = n*10 + h-'0';
  49.     #undef nxt
  50. }
  51.  
  52. const LL INF = 2e9;
  53.  
  54.  
  55. vector<LL> a;
  56. map<LL,PLL> m;
  57. int n;
  58.  
  59.  
  60.     /// O(n log n)
  61. inline void check(LL d) {
  62.     m.clear();
  63.     LL mx = 0;
  64.     LL ost;
  65.  
  66.     for (LL i:a) {
  67.         ost = (i+INF)%d;
  68.  
  69.         if ( m[ost].S ){
  70.             LL x = i - m[ost].F;
  71.             if ( !x ) continue;
  72.             if ( x == d )
  73.                 ++m[ost].S;
  74.             else
  75.                 m[ost].S = 1;
  76.  
  77.         } else
  78.             m[ost].S = 1;
  79.  
  80.         m[ost].F = i;
  81.  
  82.         if ( m[ost].S >= n ) {
  83.             cout<<i-d*(n-1)<<' '<<d<<endl;
  84.             exit(0);
  85.         }
  86.     }
  87. }
  88.  
  89.  
  90. inline void alt_check(LL d) {
  91.     vector<PLL> m(d);
  92.     for (int i=0; i<d; ++i)
  93.         m[i] = MP(0,0);
  94.  
  95.     LL mx = 0;
  96.     LL ost;
  97.  
  98.     for (LL i:a) {
  99.         ost = (i+INF)%d;
  100.  
  101.  
  102.         if ( m[ost].S ){
  103.             LL x = i - m[ost].F;
  104.             if ( !x ) continue;
  105.             if ( x == d )
  106.                 ++m[ost].S;
  107.             else
  108.                 m[ost].S = 1;
  109.  
  110.         } else
  111.             m[ost].S = 1;
  112.  
  113.         m[ost].F = i;
  114.  
  115.         if ( m[ost].S >= n ) {
  116.             cout<<i-d*(n-1)<<' '<<d<<endl;
  117.             exit(0);
  118.         }
  119.     }
  120. }
  121.  
  122.  
  123.  
  124.  
  125. inline void check_0() {
  126.     if ( n == 1 ) {
  127.         cout<<a[0]<<' '<<0<<endl;
  128.         exit(0);
  129.     }
  130.  
  131.     LL last,cnt;
  132.     last = 1e9+1;
  133.     cnt = 0;
  134.  
  135.     for (LL i:a)
  136.         if ( i == last ) {
  137.             if  ( ++cnt >= n ) {
  138.                 cout<<i<<' '<<0<<endl;
  139.                 exit(0);
  140.             }
  141.         } else {
  142.             last = i;
  143.             cnt = 1;
  144.         }
  145. }
  146.  
  147.  
  148.  
  149. map<LL,int> sum;
  150. vector<PLL> v;
  151.  
  152.  
  153. main()
  154. { file();
  155.  
  156.     //freopen("kek321.txt", "r", stdin);
  157.  
  158.     LL x;
  159.     read(x);
  160.     n = x;
  161.     a.resize(n*2);
  162.     for (int i=0; i<n*2; ++i)
  163.         read(a[i]);
  164.     sort(B_E(a));
  165.     check_0();
  166.  
  167.  
  168.     ++sum[ a[1]-a[0] ];
  169.     for (int i=2; i<n*2; ++i) {
  170.         ++sum[ a[i]-a[i-1] ];
  171.         ++sum[ a[i]-a[i-2] ];
  172.     }
  173.     sum.erase(0);
  174.     for (PLL i:sum)
  175.         v.PB( MP(-i.S, i.F) );
  176.     sort(B_E(v));
  177.  
  178.  
  179.     for (PLL i:v)
  180.         if ( i.S > n*2 )
  181.             check(i.S);
  182.         else
  183.             alt_check(i.S);
  184.  
  185.     cout<<"0 0"<<endl;
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202.  
  203.  
  204.  
  205.  
  206.  
  207.  
  208.  
  209.  
  210.  
  211.  
  212.  
  213.  
  214.  
  215.  
  216.  
  217.  
  218.  
  219.  
  220. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement