fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. inline int power(int a, int b) {
  6.     int x = 1;
  7.     while (b) {
  8.         if (b & 1) x *= a;
  9.         a *= a;
  10.         b >>= 1;
  11.     }
  12.     return x;
  13. }
  14.  
  15.  
  16. const int M = 1000000007;
  17. const int N = 3e5+9;
  18. const int INF = 2e9+1;
  19. const int LINF = 2000000000000000001;
  20.  
  21. //_ ***************************** START Below *******************************
  22.  
  23.  
  24. //? Intuition : 
  25. //*     Explore all consecutive sequence starting from x
  26. //*     How to find starting point x of any k-th consecutive seq ? 
  27. //*         If x-1 is not in array, then x is starting point of k-th seq
  28.  
  29. //* Eg : [ 0 10 2 1 3 4 11 5 8 12 6 7 13 ]
  30. //*     seq : 
  31. //*             0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
  32. //*             10 -> 11 -> 12 -> 13
  33.  
  34. //*         0 & 10 are starting point bcz -1 && 9 are not present in array
  35.  
  36. vector<int> a;
  37. void consistency(int n) {
  38. 	unordered_set<int> visited;
  39. 	unordered_set<int> isPresent;
  40.  
  41. 	for(int i=0; i<n; i++){
  42. 	    isPresent.insert(a[i]);
  43. 	}
  44. 	int maxLen = 0;
  45. 	for(auto& val : a){
  46. 	    if(visited.count(val)) continue;
  47. 	    if(isPresent.count(val-1)) continue;	
  48. 	    int startP = val;
  49. 	    int len = 0;
  50. 	    while(isPresent.count(startP)){
  51. 	        visited.insert(startP);
  52. 	        startP++;
  53. 	        len++;
  54. 	    }
  55. 	    maxLen = max(maxLen, len);	
  56. 	}	
  57.  
  58. 	cout << maxLen << endl;
  59. }
  60.  
  61. void solve() {
  62.  
  63.     int n;
  64.     cin >> n;
  65.     a.resize(n);
  66.     for(int i=0; i<n; i++) cin >> a[i];
  67.     consistency(n) ;
  68.  
  69. }
  70.  
  71.  
  72.  
  73.  
  74.  
  75. int32_t main() {
  76.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  77.  
  78.     int t = 1;
  79.     while (t--) {
  80.         solve();
  81.     }
  82.  
  83.     return 0;
  84. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
10
0 3 7 2 5 8 4 6 0 1
stdout
copy 
9
https://ideone.com/wUSZN3
language:
C++14 (gcc 8.3)
created:
10 hours ago
visibility:
public

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!