Submission #1175517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175517		zowi	A Plus B (IOI23_aplusb)	C++20	60 / 100	1107 ms	1051292 KiB

aplusb

#include<bits/stdc++.h>
using namespace std;

bool czy(int mid,vector<int> &A,vector<int> &B,int N)
{
	int p = B.size()-1;
	long long wyn =0;
	for(int i = 0;i < A.size();++i)
	{
		while(A[i]+B[p] > mid)
		{
			p--;
			if(p == -1)
			{
				break;
			}
		}
		wyn += p+1;
	}
	if(wyn >= N)
	{
		return 1;
	}
	return 0;
}


vector<int> czy1(int mid,vector<int> &A,vector<int> &B,int N)
{
	int p = B.size()-1;
	vector<int> wyn;
	for(int i = 0;i < A.size();++i)
	{
		while(A[i]+B[p] > mid)
		{
			p--;
			if(p == -1)
			{
				break;
			}
		}
		for(int j = 0;j <= p;++j)
		{
			wyn.push_back(A[i]+B[j]);
		}
	}

	sort(wyn.begin(),wyn.end());
	return wyn;

}

vector <int> smallest_sums (int N, vector <int> A, vector <int> B)
{
	long long l = 0,p = 2*(1e9),mid;
	vector<int> wyn;
	vector<int> wyn1;
	while(l < p)
	{
		mid = (l+p)/2;
		if(czy(mid,A,B,N))
		{
			p = mid;
		}
		else
		{
			l = mid+1;
		}
	}
	//cout << l;
	wyn = czy1(l,A,B,N);
	for(int i = 0;i < N;++i)
	{
		wyn1.push_back(wyn[i]);
	}
	return wyn1;
}

/*int main()
{
	vector <int> B;
	int N,n,x;
	vector <int> A;
	cin >> N;
	cin >> n;
	for(int i = 0;i < n;++i)
	{
		cin >> x;
		A.push_back(x);
	}
	for(int i = 0;i < n;++i)
	{
		cin >> x;
		B.push_back(x);
	}
	long long l = 0,p = 2*(1e9),mid;
	vector<int> wyn;
	while(l < p)
	{
		mid = (l+p)/2;
		if(czy(mid,A,B,N))
		{
			p = mid;
		}
		else
		{
			l = mid+1;
		}
	}
	//cout << l;
	wyn = czy1(l,A,B,N);
	//cout << wyn.size();
	for(int i = 0;i < N;++i)
	{
		cout << wyn[i] << ' ';
	}
}*/

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40