Submission #426202

#	Time	Username	Problem	Language	Result	Execution time	Memory
426202		frodakcin	Robots (IOI13_robots)	C++17	28 / 100	294 ms	8640 KiB

robots

#include "robots.h"
#include <cassert>
#include <algorithm>
#include <set>
#include <vector>
#include <numeric>
#include <functional>

struct BIT: std::vector<int>
{
	public:
		int S;
		BIT(int _S): S(_S), vector<int>(_S) {}
		void upd(int n, int v)
		{
			assert(0 <= n && n < S);
			for(++n;n<=S;n+=-n&n)
				at(n-1) += v;
		}
		int qry(int n)
		{
			assert(0 <= n && n <= S);
			int f=0;
			for(;n;n-=-n&n)
				f += at(n-1);
			return f;
		}
};

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
	std::sort(X, X+A, std::greater<int>());
	std::sort(Y, Y+B, std::greater<int>());
	for(int i=0;i<T;++i)
		if((A==0||W[i]>=X[0]) && (B==0||S[i]>=Y[0]))
			return -1;

	//must be possible;
	std::vector<int> ord(T);
	std::iota(ord.begin(), ord.end(), 0);
	std::sort(ord.begin(), ord.end(), [&](int u, int v){return W[u]>W[v];});

	int ans=0, j=0;
	BIT bit(B+1);
	for(int i=0;i<=A;++i)
	{
		std::vector<int> todo;
		for(;j<T && (i==A || W[ord[j]]>=X[i]);++j)
			todo.push_back(S[ord[j]]);

		std::sort(todo.begin(), todo.end(), std::greater<int>());
		for(int x:todo)
		{
			int bv = std::lower_bound(Y, Y+B, x, std::greater<int>())-Y;
			bit.upd(bv, 1);
			ans = std::max(ans, (bit.qry(bv+1)+i+bv-1)/(i+bv));
		}
	}
	return ans;
}

Compilation message (stderr)

robots.cpp: In constructor 'BIT::BIT(int)':
robots.cpp:12:7: warning: 'BIT::S' will be initialized after [-Wreorder]
   12 |   int S;
      |       ^
robots.cpp:13:37: warning:   base 'std::vector<int>' [-Wreorder]
   13 |   BIT(int _S): S(_S), vector<int>(_S) {}
      |                                     ^
robots.cpp:13:3: warning:   when initialized here [-Wreorder]
   13 |   BIT(int _S): S(_S), vector<int>(_S) {}
      |   ^~~

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