Submission #145643

#	Time	Username	Problem	Language	Result	Execution time	Memory
145643		peijar	Robots (IOI13_robots)	C++14	76 / 100	3100 ms	33884 KiB

robots

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

typedef long long ll;

const int MAXN = 1e6;

struct Jouet
{
	ll poids, taille, ind;

	bool operator<(Jouet other) const
	{
		return taille < other.taille or (taille == other.taille && (poids < other.poids or ( poids == other.poids && ind == other.ind)));
	
	}
};

Jouet jouets[MAXN];

struct dispo_taille
{
	int ind;
	
	bool operator<(dispo_taille other) const
	{
		return jouets[ind].poids < jouets[other.ind].poids
			or (jouets[ind].poids == jouets[other.ind].poids && ind < other.ind);
	}
};

ll robots_fragiles[MAXN];
ll robots_petits[MAXN];
int smallest_fragile[MAXN];
int smallest_small[MAXN];


int N, A, B;

bool can(int seconds)
{
	priority_queue<dispo_taille> Q;
	
	int r = 0;
	for (int i(0); i < N; ++i)
	{
		int next_r = smallest_small[i];
		if (next_r > r)
		{
			while (r < next_r)
			{
				int used(0);
				while (used < seconds && !Q.empty())
				{
					++used;
					Q.pop();
				}
				++r;
			}
		}
		r = next_r;
		Q.push({i});
	}
	while (r++ < B)
	{
		int used(0);
		while (used < seconds && !Q.empty())
		{
			++used;
			Q.pop();
		}
	}

	for (int i(A-1); i >= 0; --i)
	{
		int used(0);
		while (used < seconds && !Q.empty() && jouets[Q.top().ind].poids < robots_fragiles[i])
		{
			++used;
			Q.pop();
		}
	}
	return Q.empty();
}

int putaway(int a, int b, int c, int d[], int e[], int f[], int g[])
//int		main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	A = a, B = b, N = c;
	//cin >> A >> B >> N;

	for (int i(0); i < A; ++i)
		robots_fragiles[i] = d[i];
		//cin >> robots_fragiles[i];
	for (int i(0); i < B; ++i)
		robots_petits[i] = e[i]; 
		//cin >> robots_petits[i];
	sort(robots_fragiles, robots_fragiles + A);
	sort(robots_petits, robots_petits + B);

	for (int i(0); i < N; ++i)
	{
		jouets[i].poids = f[i];
		jouets[i].taille = g[i];
		//cin >> jouets[i].poids >> jouets[i].taille;
		jouets[i].ind = i;
	}

	sort(jouets, jouets + N);

	for (int i(0); i < N; ++i)
	{
		int l = 0, r = B-1;
		while (l < r)
		{
			int mid = (l+r)/2;
			if (jouets[i].taille < robots_petits[mid])
				r = mid;
			else
				l = mid+1;
		}
		if (jouets[i].taille < robots_petits[l])
			smallest_small[i] = l;
		else
			smallest_small[i] = B;
	}

	for (int i(0); i < N; ++i)
		if ((B == 0 || jouets[i].taille >= robots_petits[B-1]) && (A == 0 ||jouets[i].poids >= robots_fragiles[A-1]))
		{
//			cout << -1 << endl;
//			return 0;
			return -1;
		}

	int l(1), r(N);
	while (l < r)
	{
		int mid = (l+r)/2;
		if (can(mid))
			r = mid;
		else
			l = mid +1;
	}
	return l;
	//cout << l << endl;
}

Compilation message (stderr)

robots.cpp:1:20: warning: extra tokens at end of #include directive
 #include "robots.h";
                    ^

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 0 / 10