fork download
copy 
  1. #include <string>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <numeric>
  5. #include <set>
  6. #include <map>
  7. #include <queue>
  8.  
  9. #include<stack>
  10. #include<bitset>
  11. #include <iostream>
  12. #include <sstream>
  13. #include <cstdio>
  14. #include <cmath>
  15. #include <ctime>
  16. #include <cstring>
  17. #include <cctype>
  18. #include <cassert>
  19. #include <limits>
  20. #include <functional>
  21. #include<unordered_map>
  22.  
  23. #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
  24.  
  25. #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
  26. #define aut(r,v) for(auto r:v)
  27.  
  28. #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
  29. #define all(o) (o).begin(), (o).end()
  30. #define pb(x) push_back(x)
  31. #define pc()  pop_back()
  32.  
  33. #define ull unsigned long long
  34. #define mp(x,y) make_pair((x),(y))
  35. #define mset(m,v) memset(m,v,sizeof(m))
  36.  
  37. #define INF 0x3f3f3f3f
  38. #define INFL 0x3f3f3f3f3f3f3f3fLL
  39. using namespace std;
  40. #define endl '\n'
  41.  
  42. #define st stack<int>
  43.  
  44.  
  45.  
  46. #define vl vector<long long>
  47. #define vi vector<int>
  48. #define vb vector<bool>
  49. #define vc vector<char>
  50. #define pii pair<int,int>
  51. #define vpii vector<pii>
  52. #define vvi vector<vi>
  53. #define vs vector<string>
  54.  
  55. #define mod 1000000007
  56.  
  57. #define un  unordered_map<int,int>
  58. #define mii map<int,int>
  59.  
  60. #define Sort(a) sort(all(a))
  61. #define ED(a) Sort(a), a.erase(unique(all(a)), a.end())//removing all duplicates
  62.  
  63. #define max3(a, b, c)   max(a, max(b, c))
  64. #define min3(a, b, c)   min(a, min(b, c))
  65. #define Max(a)       *max_element(all(a))
  66. #define Min(a)       *min_element(all(a))
  67. #define MaxP(a)       max_element(all(a)) - a.begin()
  68. #define MinP(a)        min_element(all(a)) - a.begin()
  69.  
  70. #define allUpper(a)     transform(all(a), a.begin(), :: toupper)
  71. #define allLower(a)     transform(all(a), a.begin(), :: tolower)
  72.  
  73. #define rev(a)          reverse(all(a))
  74. #define ub(v,k)          upper_bound(all(v), k) - v.begin()
  75. #define lb(v,k)          lower_bound(all(v), k) - v.begin()
  76. #define adv(a,n)        advance(auto it:a,n)
  77. #define RSort(a)         sort(a.rbegin(),a.rend()) //decending order
  78. #define cnt(v,a)             count(all(v),a)
  79. #define bs(v,a)           binary_search(all(v),a)
  80. #define mmax(v)           *max_element(all(v))
  81. #define mmin(v)           *min_element(all(v))
  82. #define popcount(mask)                       __builtin_popcount(mask) // count set bit
  83. #define popcountLL(mask)                     __builtin_popcountll(mask) // for long long
  84. #define X real() // useful for working with #include <complex> for computational geometry
  85. #define Y imag()
  86. #define ll long long
  87. #define ss second
  88. #define ff first
  89.  
  90. #define trace1(x)                           cerr << #x << ": " << x << endl;
  91. #define trace2(x, y)                        cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  92. #define trace3(x, y, z)                     cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
  93. #define trace4(a, b, c, d)                  cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
  94. #define trace5(a, b, c, d, e)               cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
  95. #define trace6(a, b, c, d, e, f)            cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
  96.  
  97. template <typename T> T gcd(T a, T b) { while (b) b ^= a ^= b ^= a %= b; return a; }
  98. template <typename T> T setbit(T mask, T pos) { return mask |= (1 << pos); }
  99. template <typename T> T resetbit(T mask, T pos) { return mask &= ~(1 << pos); }
  100. template <typename T> T togglebit(T mask, T pos) { return mask ^= (1 << pos); }
  101. template <typename T> T checkbit(T mask, T pos) { return (bool)(mask & (1 << pos)); }
  102. template <typename T> T lcm(T a, T b) { return (a / gcd(a, b)) * b; }
  103.  
  104.  
  105.  
  106. template <typename T> T modu(T a, T b) { return (a < b ? a : a % b); }
  107. template<typename T> T mod_neg(T a, T b) { a = mod(a, b); if (a < 0) { a += b; } return a; }
  108.  
  109. template <typename T>T expo(T e, T n) { T x = 1, p = e; while (n) { if (n & 1)x = x * p; p = p * p; n >>= 1; } return x; }
  110. template<typename T> T mod_inverse(T a, T n) { T x, y; T d = extended_euclid(a, n, x, y); return (d > 1 ? -1 : mod_neg(x, n)); }
  111.  
  112. template <typename T>T power(T e, T n, T m) { T x = 1, p = e; while (n) { if (n & 1)x = mod(x * p, m); p = mod(p * p, m); n >>= 1; } return x; }
  113. template <typename T>T powerL(T e, T n, T m) { T x = 1, p = e; while (n) { if (n & 1)x = mulmod(x, p, m); p = mulmod(p, p, m); n >>= 1; } return x; }
  114.  
  115. bool Pow2(int n) {
  116.     return n && (!(n & (n - 1)));
  117. }
  118. void printc(vc& result) {
  119.     aut(r, result) cout << r << " ";
  120.     cout << endl;
  121. }
  122. void printl(vl& result) {
  123.     aut(r, result) cout << r << " ";
  124.     cout << endl;
  125. }
  126. void print(vi& result) {
  127.     aut(r, result) cout << r << " ";
  128.     cout << endl;
  129. }
  130. // Recursively computes the power
  131. int binpow(int a, int b)
  132. {
  133.     if (b == 0)
  134.         return a;
  135.     int res = binpow(a, b / 2);
  136.     if (b % 2)
  137.         return res * res * a;
  138.     else
  139.         return res * res;
  140. }
  141. // iteratively computes the power
  142. ll pow(ll a, ll b)
  143. {
  144.     ll res = 1;
  145.     while (b)
  146.     {
  147.         if (b & 1)
  148.             res = res * a;
  149.         a = a * a;
  150.         b >>= 1;
  151.     }
  152.     return res;
  153. }
  154. int modpow(int a, int b, int m)
  155. {
  156.     int ans = 1;
  157.     while (b)
  158.     {
  159.         if (b & 1)
  160.             ans = (ans * a) % m;
  161.         b /= 2;
  162.         a = (a * a) % m;
  163.     }
  164.     return ans;
  165. }
  166.  
  167. ll ncr(ll n, ll k)
  168. {
  169.     ll res = 1;
  170.  
  171.     // Since C(n, k) = C(n, n-k) 
  172.     if (k > n - k)
  173.         k = n - k;
  174.  
  175.     // Calculate value of 
  176.     // [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1] 
  177.     for (ll i = 0; i < k; ++i) {
  178.         res *= (n - i);
  179.         res /= (i + 1);
  180.     }
  181.  
  182.     return res;
  183. }
  184. //ifstream cin("b_read_on.txt"); ofstream cout("output3.txt");
  185. //Use (<<) for multiplication
  186. //Use (>>) for division
  187. //ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cout<<fixed;cerr.tie(NULL);
  188. // find_by_order -> value at index
  189. // order_of_key -> index of value
  190. // while using (1<<i) use ((ll)1<<(ll)i) 
  191. // in Floyd-Warshall Algo, k is outer loop 
  192. // If an element was not initially in map and if asked mp[a],the element gets inserted 
  193. // a%=mod take a lot of time... try to use it minimum and use memset as it reduces a lot of time usage...use if(a>=mod) a%=mod
  194. //cout<<(double) can be harmful , always use printf(%.9llf)...take scanf("%lf",&p[i][j]) as input , not llf;
  195. //use s.erase(it++) for erasing iterator and then moving to the next one
  196. //never use adj.resize(n) as value is persistent, always erase
  197. //use __builtin_popcountll() for ll
  198. // no of prime numbers in range : (70,19) , (1000,168) , (100000,1229) , (sqrt(10^9),3409) ;
  199. //always check the use of segment tree using bottom-up dp
  200. int dx[] = { 0, 0, 1, -1 };
  201. int dy[] = { 1, -1, 0, 0 }; // 4 Direction
  202. /* int dx[] = {1,-1,0,0,1,1,-1,-1} , dy[] = {0,0,1,-1,1,-1,1,-1}; */ // 8 Direction
  203. /* int dx[] = {1,-1,1,-1,2,2,-2,-2} , dy[] = {2,2,-2,-2,1,-1,1,-1}; */ // Knight Direction
  204. /* int dx[] = {2,-2,1,1,-1,-1} , dy[] = {0,0,1,-1,1,-1}; */ // Hexagonal Direction
  205.  
  206.  
  207.  
  208.  
  209. vb vis(1001);
  210. int main() {
  211.     ios_base::sync_with_stdio(false);
  212.     cin.tie(NULL);
  213.     cout.tie(NULL);
  214.     int test;
  215.     test = 1;
  216.     // cin >> test;
  217.  
  218.     while (test--) {
  219.         int n;
  220.         cin >> n;
  221.         vi v(n);
  222.         rep(i, n) cin >> v[i];
  223.         RSort(v);
  224.         vpii vp;
  225.         rep(i, n - 1) {
  226.             vp.push_back({ v[i] - v[i + 1] - 2 ,v[i] - v[i + 1] + 2 });
  227.         }
  228.         int maxi = max(vp[0].ff, vp[0].ss);
  229.         int mini = min(vp[0].ss, vp[0].ff);
  230.         int flag = 0;
  231.  
  232.         for (int i = 0; i < vp.size(); i++) {
  233.             int m = max(vp[i].ff, vp[i].ss);
  234.             int l = min(vp[i].ff, vp[i].ss);
  235.             if (l > maxi || m < mini) {
  236.                 flag = 1;
  237.                 break;
  238.             }
  239.             else maxi = min(maxi, m);
  240.             mini = max(mini, l);
  241.         }
  242.         trace2(maxi, mini);
  243.         if (flag == 1) cout << -1 << endl;
  244.         else {
  245.             int count = 0;
  246.             unordered_map<int, int> mp;
  247.             for (int i = 0; i < n - 1; i++) {
  248.                 if (v[i] - v[i + 1] <= maxi && v[i] - v[i + 1] >= mini) mp[v[i] - v[i + 1]]++;
  249.                 else count++;
  250.             }
  251.             if (mp.size() >= 2) count += mp.size() - 1;
  252.             cout << count << endl;
  253.  
  254.         }
  255.  
  256.     }
  257.  
  258. }
  259.  
  260.  
Success #stdin #stdout #stderr 0s 4560KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 
maxi: 2 | mini: -2
https://ideone.com/Ab0k6C
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!