This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (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();
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |