제출 #373158

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
373158		luciocf	로봇 (IOI13_robots)	C++14	76 / 100	364 ms	65540 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];
 
bool mark[maxn];
 
bool ok(int k)
{
	set<pii> st[maxn];
	for (int i = 1; i <= max(n, 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;
	multiset<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});
	}
 
	vector<int> v;
	for (int i = 1; i <= t; i++)
		if (!mark[i])
			v.push_back(toy[i].ss);
 
	sort(v.begin(), v.end());
 
	ptr = m;
	int qtd = 0;
 
	for (int i = v.size()-1; i >= 0; i--)
	{
		if (qtd == k) ptr--, qtd = 0;
		if (ptr == 0 || y[ptr] < v[i]) 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);
 
    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;
}

컴파일 시 표준 에러 (stderr) 메시지

robots.cpp: In function 'bool ok(int)':
robots.cpp:31: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]
   31 |   if (st[ptr].size() == k) ptr--;
      |       ~~~~~~~~~~~~~~~^~~~
robots.cpp:66: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]
   66 |   if (st[j].size() == k)
      |       ~~~~~~~~~~~~~^~~~

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