reiziger

Untitled

Aug 23rd, 2019
78
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _FORTIFY_SOURCE 0
  2. #pragma GCC optimize("Ofast")
  3. #pragma GCC optimize("no-stack-protector")
  4. #pragma GCC optimize("unroll-loops")
  5. #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
  6. #pragma GCC optimize("fast-math")
  7.  
  8. #include <iostream>
  9. #include <math.h>
  10. #include <algorithm>
  11. #include <iomanip>
  12. #include <vector>
  13. #include <set>
  14. #include <map>
  15. #include <deque>
  16. #include <stack>
  17. #include <unordered_map>
  18.  
  19. using namespace std;
  20.  
  21. typedef long long ll;
  22. typedef long double ld;
  23. typedef pair<ll, ll> pl;
  24. typedef pair<ld, ld> pd;
  25.  
  26. const ll N = 1 * 1e7 + 100;
  27. const ll M = 1e4 + 100;
  28. const ll INF = 1e18 + 100;
  29.  
  30. #define x first
  31. #define y second
  32. #define pb push_back
  33.  
  34. int firstMissingPositive(vector<int>& nums) {
  35. int32_t ans = 1;
  36. int32_t k = INT32_MAX;
  37. int32_t s = -1;
  38.  
  39. for (const int32_t num : nums) {
  40. if (num > 0) {
  41. if (num == ans) {
  42. ans++;
  43. } else if (num > ans) {
  44. if (num - ans < k) {
  45. k = min(k, num - ans);
  46. s = num;
  47. }
  48. }
  49. }
  50. }
  51.  
  52. cout << "s = " << s << endl;
  53. cout << "k = " << k << endl;
  54. cout << "ans = '" << ans << endl;
  55.  
  56. return s == ans ? s + 1 : ans;
  57. }
  58.  
  59. int main() {
  60. int n;
  61.  
  62. cin >> n;
  63. vector<int> a(n);
  64.  
  65. for (int i = 0; i < n; i++) {
  66. cin >> a[i];
  67. }
  68.  
  69. cout << firstMissingPositive(a);
  70. return 0;
  71. }
RAW Paste Data