767D - Cartons of milk - CodeForces Solution

//The more it is difficult the more it is gonna be satisfying at the end
# pragma GCC target ("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
# include <iostream>
# include <algorithm>
# include <cstring>
# include <string>
# include <iomanip>
# include <vector>
# include <cmath>
# include <map>
# include <unordered_map>
# include <set>
# include <queue>
# include <deque>
# include <bitset>
# include <stack>
# define mod int(1e9+7)
# define SimplyFast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
int n, m, k;
int mx = 0;
vector<int>Had;
vector<pair<int, int>>Shop;
vector<int>freq(1e7 + 1);
bool can(int mid)
{
	for (int i = 0; i <= mx; i++)
	{
		freq[i] = 0;
	}
	for (int i = 1; i <= Had.size() - 1; i++)
	{
		freq[Had[i]]++;
	}
	for (int i = m - mid + 1; i <= m; i++)
	{
		freq[Shop[i].first]++;
	}
	int day = 0;
	int c = 0;
	int p = 0;
	while (p <= mx)
	{
		while (freq[p])
		{
			if (freq[p] and p < day)
			{
				return false;
			}
			if (c == k)
			{
				day++;
				c = 0;
			}
			else
			{
				freq[p]--;
				c++;
			}
		}
		p++;
	}
	return true;
}
int main()
{
	SimplyFast;
	cin >> n >> m >> k;
	Had = vector<int>(n + 1);
	Shop = vector<pair<int, int>>(m + 1);
	for (int i = 1; i <= n; i++)
	{
		cin >> Had[i];
		mx = max(mx, Had[i]);
	}
	for (int i = 1; i <= m; i++)
	{
		cin >> Shop[i].first;
		Shop[i].second = i;
		mx = max(mx, Shop[i].first);
	}
	sort(Shop.begin(), Shop.end());
	int l = 0, r = m, ans = -1;
	while (l <= r)
	{
		int mid = (l + r) / 2;
		if (can(mid))
		{
			ans = mid;
			l = mid + 1;
		}
		else
		{
			r = mid - 1;
		}
	}
	if (ans == -1)
	{
		cout << -1 << "\n";
		return 0;
	}
	vector<int>vec;
	for (int i = m - ans + 1; i <= m; i++)
	{
		vec.push_back(Shop[i].second);
	}
	cout << vec.size() << "\n";
	for (auto &it : vec)
	{
		cout << it << ' ';
	}
	cout << "\n";
	return 0;
}