ural 1252. Sorting the Tombstones

  1 /**
  2 Create By yzx - stupidboy
  3 */
  4 #include <cstdio>
  5 #include <cstring>
  6 #include <cstdlib>
  7 #include <cmath>
  8 #include <deque>
  9 #include <vector>
 10 #include <queue>
 11 #include <iostream>
 12 #include <algorithm>
 13 #include <map>
 14 #include <set>
 15 #include <ctime>
 16 #include <iomanip>
 17 using namespace std;
 18 typedef long long LL;
 19 typedef double DB;
 20 #define MIT (2147483647)
 21 #define INF (1000000001)
 22 #define MLL (1000000000000000001LL)
 23 #define sz(x) ((int) (x).size())
 24 #define clr(x, y) memset(x, y, sizeof(x))
 25 #define puf push_front
 26 #define pub push_back
 27 #define pof pop_front
 28 #define pob pop_back
 29 #define ft first
 30 #define sd second
 31 #define mk make_pair
 32 
 33 inline int Getint()
 34 {
 35     int Ret = 0;
 36     char Ch = ‘ ‘;
 37     bool Flag = 0;
 38     while(!(Ch >= ‘0‘ && Ch <= ‘9‘))
 39     {
 40         if(Ch == ‘-‘) Flag ^= 1;
 41         Ch = getchar();
 42     }
 43     while(Ch >= ‘0‘ && Ch <= ‘9‘)
 44     {
 45         Ret = Ret * 10 + Ch - ‘0‘;
 46         Ch = getchar();
 47     }
 48     return Flag ? -Ret : Ret;
 49 }
 50 
 51 const int N = 130010;
 52 int n, arr[N], order[N];
 53 int ans;
 54 
 55 inline void Input()
 56 {
 57     scanf("%d", &n);
 58     for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
 59 }
 60 
 61 inline int Gcd(int a, int b)
 62 {
 63     if(b) return Gcd(b, a % b);
 64     else return a;
 65 }
 66 
 67 inline int Work(int *arr, int *order, int n)
 68 {
 69     int ret = 0;
 70     for(int i = 0; i < n; i++)
 71     {
 72         int idx = lower_bound(order, order + n, arr[i]) - order;
 73         int delta = abs(i - idx);
 74         ret = Gcd(ret, delta);
 75     }
 76     return ret;
 77 }
 78 
 79 inline void Solve()
 80 {
 81     ans = 0;
 82     for(int i = 0; i < n; i++) order[i] = arr[i];
 83     sort(order, order + n);
 84     int t1 = Work(arr, order, n);
 85     for(int i = 0; i < n; i++) arr[i] = order[i] = - arr[i];
 86     sort(order, order + n);
 87     int t2 = Work(arr, order, n);
 88     if(!t1 || !t2) ans = n;
 89     else ans = max(t1, t2);
 90     
 91     printf("%d\n", ans - 1);
 92 }
 93 
 94 int main()
 95 {
 96     freopen("a.in", "r", stdin);
 97     Input();
 98     Solve();
 99     return 0;
100 }