SHARE
TWEET

Untitled

reiziger Aug 23rd, 2019 68 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top