Submission #373164

#	Time	Username	Problem	Language	Result	Execution time	Memory
373164		luciocf	Robots (IOI13_robots)	C++14	100 / 100	2821 ms	65536 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];
 
int ind[maxn], sz[maxn];
vector<pii> st[50010];
 
bool ok(int k)
{
	for (int i = 1; i <= n; i++)
		st[i].clear(), sz[i] = 0;

	for (int i = 1; i <= t; i++)
		mark[i] = 0;
 
	int ptr = n;
 
	for (int i = t; i >= 1; i--)
	{
		if (sz[ptr] == k) ptr--;
		if (ptr == 0) break;
		if (x[ptr] < toy[i].ff) continue;
 
		mark[i] = 1;
		st[ptr].push_back({toy[i].ss, i}), sz[ptr]++;
	}

	for (int i = 1; i <= n; i++)
	{
		ind[i] = 0;
		sort(st[i].begin(), st[i].end());
	}
 
	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;
 
		auto it = candidatos.lower_bound({toy[i].ff, 0});
		if (it == candidatos.end())
		{
			pq.pop();
			continue;
		}
 
		int j = it->ss;
 
		if (ind[j] == st[j].size() || st[j][ind[j]].ff >= toy[i].ss)
		{
			candidatos.erase({x[j], j});
			continue;
		}

		pq.pop();
 
		if (sz[j] == k)
		{
			mark[st[j][ind[j]].ss] = 0;
 
			pq.push(st[j][ind[j]]);
 
			ind[j]++;
		}
		else sz[j]++;
 
		mark[i] = 1;
	}
 
	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] = {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:72:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   if (ind[j] == st[j].size() || st[j][ind[j]].ff >= toy[i].ss)
      |       ~~~~~~~^~~~~~~~~~~~~~~

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