Submission #373161

#	Time	Username	Problem	Language	Result	Execution time	Memory
373161		luciocf	Robots (IOI13_robots)	C++14	0 / 100	3 ms	2668 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
 
#define ff first
#define ss second
 
using namespace std;
 
typedef pair<int, int> pii;
 
const int maxn = 1e6+10;
 
int n, m, t;
int x[maxn], y[maxn];
 
pii toy[maxn], toy2[maxn];
 
bool mark[maxn];
 
set<pii> st[50010];
 
bool ok(int k)
{
	for (int i = 1; i <= n; i++)
		st[i].clear();

	for (int i = 1; i <= t; i++)
		mark[i] = 0;
 
	int ptr = n;
	int tot = 0;
 
	for (int i = t; i >= 1; i--)
	{
		if (st[ptr].size() == k) ptr--;
		if (ptr == 0) break;
		if (x[ptr] < toy[i].ff) continue;
 
		mark[i] = 1;
		++tot;
		st[ptr].insert({toy[i].ss, i});
	}
 
	priority_queue<pii> pq;
	set<pii> candidatos;
 
	for (int i = 1; i <= t; i++)
		if (!mark[i])
			pq.push({toy[i].ss, i});
 
	for (int i = 1; i <= n; i++)
		candidatos.insert({x[i], i});
 
	while (!pq.empty())
	{
		int i = pq.top().ss; pq.pop();
 
		auto it = candidatos.lower_bound({toy[i].ff, 0});
		if (it == candidatos.end()) continue;
 
		int j = it->ss;
 
		if (st[j].begin()->ff >= toy[i].ss)
		{
			candidatos.erase({x[j], j});
			pq.push({toy[i].ss, i});
			continue;
		}
 
		if (st[j].size() == k)
		{
			mark[st[j].begin()->ss] = 0;
 
			pq.push(*st[j].begin());
 
			st[j].erase(st[j].begin());
		}
 
		mark[i] = 1;
		st[j].insert({toy[i].ss, i});
	}
 
	ptr = m;
	int qtd = 0;

	for (int i = t; i >= 1; i--)
	{
		if (mark[toy2[i].ss]) continue;

		if (qtd == k) ptr--, qtd = 0;
		if (ptr == 0 || y[ptr] < toy2[i].ff) return 0;
		
		qtd++;	
	}
 
	return 1;
}
 
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    n = A, m = B, t = T;
 
    for (int i = 0; i < n; i++)
    	x[i+1] = X[i]-1;
 
    for (int i = 0; i < m; i++)
    	y[i+1] = Y[i]-1;
 
    for (int i = 0; i < t; i++)
    	toy[i+1] = {W[i], S[i]};
 
    sort(x+1, x+n+1); sort(y+1, y+m+1); sort(toy+1, toy+t+1);

    for (int i = 1; i <= t; i++)
    	toy2[i+1] = {toy[i].ss, i};

    sort(toy2+1, toy2+t+1);
 
    int ini = 1, fim = t, ans = -1;
 
    while (ini <= fim)
    {
    	int mid = (ini+fim)>>1;
 
    	if (ok(mid)) ans = mid, fim = mid-1;
    	else ini = mid+1;
    }
 
    return ans;
}

Compilation message (stderr)

robots.cpp: In function 'bool ok(int)':
robots.cpp:35:22: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |   if (st[ptr].size() == k) ptr--;
      |       ~~~~~~~~~~~~~~~^~~~
robots.cpp:70:20: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |   if (st[j].size() == k)
      |       ~~~~~~~~~~~~~^~~~

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