oj.uz

Submission #150852

# Submission time Handle Problem Language Result Execution time Memory
150852 2019-09-01T08:59:46 Z etyu(#3586, kimjihoon) King of Chairs (FXCUP4_chairs) C++17
95 / 100
 203 ms 7496 KB 
#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;
}

#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1056 KB Correct
2 Correct 11 ms 1056 KB Correct
3 Correct 11 ms 1016 KB Correct
4 Correct 11 ms 1056 KB Correct
5 Correct 11 ms 1056 KB Correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 4460 KB Correct
2 Correct 142 ms 7056 KB Correct
3 Correct 138 ms 7360 KB Correct
4 Correct 153 ms 7428 KB Correct
5 Correct 156 ms 7408 KB Correct
6 Correct 160 ms 7276 KB Correct
7 Correct 151 ms 7372 KB Correct

Subtask #3
40.0 / 45.0

# Verdict Execution time Memory Grader output
1 Partially correct 96 ms 4468 KB B = 50991
2 Partially correct 172 ms 7052 KB B = 91406
3 Partially correct 174 ms 7316 KB B = 49847
4 Partially correct 180 ms 7496 KB B = 99850
5 Partially correct 203 ms 7488 KB B = 99598
6 Partially correct 190 ms 7480 KB B = 99746
7 Partially correct 184 ms 7372 KB B = 49910
8 Correct 110 ms 7384 KB Correct