oj.uz

Submission #150708

# Submission time Handle Problem Language Result Execution time Memory
150708 2019-09-01T08:50:57 Z etyu(#3586, kimjihoon) King of Chairs (FXCUP4_chairs) C++17
95 / 100
 197 ms 7104 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, int> > p;
void Init(long long B, std::vector<int> C) {
	N = C.size();
	BB = B;
	p.push_back(std::make_pair(-1, -1));
	for (int i = 0; i < N; i++) 
		p.push_back(std::make_pair(C[i], i));
	p.push_back(std::make_pair(1000000000, N));
	sort(p.begin(), p.end());
}

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, -10))).second;
	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;
}

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 12 ms 1056 KB Correct
2 Correct 13 ms 1052 KB Correct
3 Correct 10 ms 796 KB Correct
4 Correct 10 ms 1064 KB Correct
5 Correct 11 ms 1056 KB Correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 4204 KB Correct
2 Correct 141 ms 6560 KB Correct
3 Correct 140 ms 6864 KB Correct
4 Correct 155 ms 7096 KB Correct
5 Correct 154 ms 7096 KB Correct
6 Correct 162 ms 6848 KB Correct
7 Correct 157 ms 6868 KB Correct

Subtask #3
40.0 / 45.0

# Verdict Execution time Memory Grader output
1 Partially correct 96 ms 4212 KB B = 50991
2 Partially correct 174 ms 6496 KB B = 91406
3 Partially correct 175 ms 6860 KB B = 49847
4 Partially correct 192 ms 6996 KB B = 99850
5 Partially correct 190 ms 7096 KB B = 99598
6 Partially correct 197 ms 7104 KB B = 99746
7 Partially correct 176 ms 6848 KB B = 49910
8 Correct 116 ms 6856 KB Correct