Advertisement
Guest User

Untitled

a guest
Dec 13th, 2018
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cmath>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 1e5 + 10;
  8. int n, s1[N], s2[N], sum[N];
  9. pair<int, int> a[N];
  10.  
  11. int main()
  12. {
  13. cin >> n;
  14. for (int i = 0; i < n; ++i)
  15. {
  16. cin >> a[i].first;
  17. a[i].second = i;
  18. }
  19. sort(a, a + n);
  20. reverse(a, a + n);
  21. sum[0] = a[0].first;
  22. int t = 0, s = 0;
  23. s1[t++] = a[0].first;
  24. for (int i = 1; i < n; ++i)
  25. {
  26. if ((sum[t - 1] + a[i].first <= n - t) && (!((a[i].first == 0) && (sum[t - 1] + a[i].first < n - t))))
  27. {
  28. sum[t] = sum[t - 1] + a[i].first;
  29. s1[t++] = a[i].second;
  30. }
  31. else
  32. {
  33. s2[s++] = a[i].second;
  34. }
  35. }
  36. if (sum[t - 1] != n - t)
  37. {
  38. cout << "NO";
  39. return 0;
  40. }
  41. for (int i = 0; i < t; ++i)
  42. {
  43. a[s1[i]].first = 1;
  44. }
  45. for (int i = 0; i < s; ++i)
  46. {
  47. a[s2[i]].first = 2;
  48. }
  49. cout << "YES\n";
  50. for (int i = 0; i < n; ++i)
  51. {
  52. cout << a[i].first << ' ';
  53. }
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement