Advertisement
Galebickosikasa

Untitled

Oct 13th, 2020
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.93 KB | None | 0 0
  1. // #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
  2. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx")
  3. // #pragma comment(linker, "/stack:200000000"]
  4.  
  5. #include <iostream>
  6. #include <vector>
  7. #include <cmath>
  8. #include <algorithm>
  9. #include <unordered_set>
  10. #include <unordered_map>
  11. #include <set>
  12. #include <map>
  13. #include <queue>
  14. #include <deque>
  15. #include <bitset>
  16. #include <stack>
  17. #include <random>
  18. #include <fstream>
  19. #include <sstream>
  20. #include <chrono>
  21.  
  22. #define fi first
  23. #define se second
  24. #define pb push_back
  25. #define ll long long
  26. #define ld long double
  27. #define hm unordered_map
  28. #define pii pair<int, int>
  29. #define sz(a) (int)a.size()
  30. #define all(a) a.begin(), a.end()
  31. #define cinv(v) for (auto& x: v) cin >> x
  32. #define fr(i, n) for (int i = 0; i < n; ++i)
  33. #define fl(i, l, n) for (int i = l; i < n; ++i)
  34.  
  35. #define int ll
  36.  
  37. template <typename T1, typename T2> inline bool chkmin(T1 &x, const T2 &y) {if (x > y) {x = y; return 1;} return 0;}
  38. template <typename T1, typename T2> inline bool chkmax(T1 &x, const T2 &y) {if (x < y) {x = y; return 1;} return 0;}
  39.  
  40. using namespace std;
  41.  
  42. #ifdef __LOCAL
  43. #define dbg(x) cerr << #x << " : " << x << '\n'
  44. const int maxn = 20;
  45. #else
  46. #define dbg(x)
  47. const int maxn = 2e5 + 20;
  48. #endif
  49.  
  50. //tg: @galebickosikasa
  51.  
  52. ostream& operator << (ostream& out, vector<int>& v) {
  53. for (auto& x: v) out << x << ' ';
  54. return out;
  55. }
  56.  
  57. ostream& operator << (ostream& out, pii& v) {
  58. out << v.fi << ", " << v.se;
  59. return out;
  60. }
  61.  
  62. istream& operator >> (istream& in, pii& a) {
  63. in >> a.fi >> a.se;
  64. return in;
  65. }
  66.  
  67. const ll inf = (ll) 2e9;
  68. const ld pi = asin (1) * 2;
  69. const ld eps = 1e-8;
  70. const ll mod = (ll)1e9 + 7;
  71. const ll ns = 97;
  72.  
  73. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  74.  
  75. struct kek {
  76. int x, i;
  77.  
  78. bool operator < (const kek& other) const {
  79. return x < other.x;
  80. }
  81. };
  82.  
  83. signed main () {
  84. ios_base::sync_with_stdio(false);
  85. cin.tie(nullptr);
  86. cout.tie(nullptr);
  87. int n, m, k;
  88. cin >> n >> m >> k;
  89. vector<int> goo (n), moo (m);
  90. cinv (goo);
  91. cinv (moo);
  92. sort (all (goo));
  93. sort (all (moo));
  94. int delta = inf;
  95. for (int i = k - 1; i < n; i += k) {
  96. chkmin (delta, goo[i] - i / k);
  97. }
  98. chkmin (delta, goo.back () - (n - 1) / k);
  99. if (delta < 0) {
  100. cout << -1;
  101. exit (0);
  102. }
  103. vector<kek> a (n), b (m);
  104. fr (i, n) a[i] = {goo[i], -1};
  105. fr (i, m) b[i] = {moo[i], i};
  106. stack<kek> t;
  107. vector<kek> lol (n + m);
  108. merge (all (a), all (b), lol.begin ());
  109. int cnt = 0;
  110. fr (i, sz (lol)) {
  111. dbg (lol[i].x);
  112. dbg (lol[i].i);
  113. dbg (cnt);
  114. dbg (cnt / k);
  115. if (lol[i].x >= cnt / k) {
  116. if (lol[i].i != -1) t.push (lol[i]);
  117. ++cnt;
  118. } else {
  119. if (lol[i].i == -1) {
  120. while (lol[i].x < cnt / k) {
  121. t.pop ();
  122. --cnt;
  123. }
  124. ++cnt;
  125. }
  126. }
  127. // ++cnt;
  128. }
  129. cout << sz (t) << '\n';
  130. while (!t.empty ()) {
  131. cout << t.top ().i + 1 << ' ';
  132. t.pop ();
  133. }
  134.  
  135.  
  136.  
  137.  
  138.  
  139.  
  140. }
  141.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement