fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. // int mex(vector<int> &arr){
  7. // 	int ans=0;
  8. // 	int n=arr.size();
  9. // 	unordered_map<int,int> mpp;
  10.  
  11. // 	for(int i=0;i<n;i++){
  12. // 		mpp[arr[i]]++;
  13. // 		while(mpp.find(ans)!=mpp.end()){
  14. // 			ans++;
  15. // 		}
  16. // 	}
  17. // 	return ans;
  18.  
  19. // }
  20.  
  21. int main() {
  22. 	// your code goes here
  23. 	int n;
  24. 	cin>>n;
  25. 	vector<int> arr(n);
  26. 	for(int i=0;i<n;i++){
  27. 		cin>>arr[i];
  28. 	}
  29.  
  30. 	vector<int> suffix(n,0);
  31. 	vector<int> answer(n,0);
  32. 	vector<int> result;
  33.  
  34.  
  35.     int mex=0;
  36.     unordered_map<int,int> mpp;
  37.  
  38.  
  39. 	for(int i=n-1;i>=0;i--){
  40. 		mpp[arr[i]]++;
  41. 		while(mpp.find(mex)!=mpp.end()){
  42. 			mex++;
  43. 		}
  44. 		suffix[i]=mex;
  45. 	}
  46. 	answer[n-1]=n-1;
  47. 	mpp.clear();
  48.     mpp[arr[n-1]]++;
  49.  
  50. 	for(int i=n-2;i>=0;i--){
  51. 		mpp[arr[i]]++;
  52.  
  53. 		if(suffix[i]==suffix[i+1]){
  54. 			int j=answer[i+1];
  55. 			while(true){
  56. 				mpp[arr[j]]--;
  57. 				if(mpp[arr[j]]==0){
  58. 					mpp[arr[j]]++;
  59. 					break;
  60. 				}
  61. 				else{
  62. 					j--;
  63. 				}
  64. 			}
  65. 			answer[i]=j;
  66. 		}
  67. 		else{
  68. 			answer[i]=answer[i+1];
  69. 		}
  70. 	}
  71.  
  72. 	int j=0;
  73. 	while(j<n){
  74. 		int a = suffix[j];
  75. 		result.push_back(a);
  76. 		j = answer[j]+1;
  77.  
  78. 	}
  79.  
  80. 	for(int i=0;i<result.size();i++){
  81. 		cout<<result[i]<<endl;
  82.  
  83. 	}
  84.  
  85.  
  86.  
  87.  
  88. 	return 0;
  89. }
Success #stdin #stdout 0.01s 5352KB
comments (?)
stdin
copy 
2
0 5
stdout
copy 
1
https://ideone.com/l6hGfi
language:
C++14 (gcc 8.3)
created:
3 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!