Submission #150852

#	Time	Username	Problem	Language	Result	Execution time	Memory
150852		etyu (#200)	King of Chairs (FXCUP4_chairs)	C++17	95 / 100	203 ms	7496 KiB

king

#include "king.h"
#include <algorithm>

long long SendInfo(std::vector<int> W, std::vector<int> C) {
	int N = W.size();
	sort(W.begin(), W.end()); sort(C.begin(), C.end());
	long long ans = 0;
	int p = (int)C.size() - 1;
	for (int i = (int)W.size() - 1; i >= 0; i--) {
		if (p < 0) break;
		if (C[p] >= W[i]) {
			p--; ans++;
		}
	}
	return ans;
}

vassal

#include "vassal.h"
#include <algorithm>
#include <utility>
#include <iostream>

long long BB;
int N, ft[100009];
std::vector<std::pair<int, std::pair<int, int> > > p;
void Init(long long B, std::vector<int> C) {
	N = C.size();
	BB = B;
	p.push_back(std::make_pair(-1, std::make_pair(-1, -1)));
	for (int i = 0; i < N; i++) 
		p.push_back(std::make_pair(C[i], std::make_pair(i, -1)));
	p.push_back(std::make_pair(1000000000, std::make_pair(N, -1)));
	sort(p.begin(), p.end());
	for (int i = 0; i <= N + 1; i++)
		p[i].second.second = i;
}

void up(int i)
{
	while (i <= N + 1) {
		ft[i]++;
		i += (i & (-i));
	}
}

int sum(int i)
{
	int s = 0;
	while (i)
	{
		s += ft[i];
		i -= (i & (-i));
	}
	return s;
}

int bs(int s, int e, int t)
{
	int md = (s + e) / 2;
	if (s >= e) return md;
	if (sum(md) - sum(t) == md - t) return bs(md + 1, e, t);
	return bs(s, md, t);
}

int Maid(int W) {
	int t = (*std::lower_bound(p.begin(), p.end(), std::make_pair(W, std::make_pair(-10, -10)))).second.second - 1;
	if (N - t > BB) t = N - BB;
	int r = bs(t + 1, N + 1, t);
	if (r == N + 1) return -1;
	up(r);
	return p[r].second.first;
}

Compilation message (stderr)

king.cpp: In function 'long long int SendInfo(std::vector<int>, std::vector<int>)':
king.cpp:5:6: warning: unused variable 'N' [-Wunused-variable]
  int N = W.size();
      ^

• Subtask 1: 17 / 17
• Subtask 2: 38 / 38
• Subtask 3: 40 / 45