Submission #813573

#	Time	Username	Problem	Language	Result	Execution time	Memory
813573		I_Love_EliskaM_	Robots (IOI13_robots)	C++17	14 / 100	2638 ms	30572 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;

struct toy {
	int w,s,i;
};

bool foo(toy a, toy b) {
	return a.w < b.w;
}

int check(int a, int b, int t, vector<int> x, vector<int> y, vector<int> w, vector<int> s, int mid) {
	int tot=0;

	vector<int> vis(t);
	vector<toy> v;
	forn(i,t) v.pb({w[i],s[i],i});
	sort(all(v),foo);
	int p=0;

	priority_queue<pi> q;
	forn(i,a) {
		while (p<v.size() && v[p].w<x[i]) {
			q.push({v[p].s,i});
			++p;
		}
		forn(iter,mid) {
			if (!q.size()) break;
			auto it=q.top(); q.pop();
			vis[it.s]=1;
			++tot;
		}
	}

	v.clear();
	while (q.size()) q.pop();
	forn(i,t) if (!vis[i]) v.pb({s[i],w[i],i});
	p=0;

	forn(i,b) {
		while (p<v.size() && v[p].w<y[i]) {
			q.push({v[p].s,i});
			++p;
		}
		forn(iter,mid) {
			if (!q.size()) break;
			auto it=q.top(); q.pop();
			vis[it.s]=1;
			++tot;
		}
	}

	return tot==t;
}

int putaway(int a, int b, int t, int X[], int Y[], int W[], int S[]) {
	
	vector<int> x,y,w,s;
	forn(i,a) x.pb(X[i]);
	forn(i,b) y.pb(Y[i]);
	forn(i,t) w.pb(W[i]),s.pb(S[i]);
	sort(all(x));
	sort(all(y));

	int l=0, r=t+1;
	while (l<r) {
		int mid=(l+r)>>1;
		if (check(a,b,t,x,y,w,s,mid)) r=mid;
		else l=mid+1;
	}
	if (r==t+1) return -1;
	return r;

}

Compilation message (stderr)

robots.cpp: In function 'int check(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int)':
robots.cpp:31:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   while (p<v.size() && v[p].w<x[i]) {
      |          ~^~~~~~~~~
robots.cpp:49:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   while (p<v.size() && v[p].w<y[i]) {
      |          ~^~~~~~~~~

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