#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 cansitbegin = -2;
long long cansitend = -2;
int X = n - 1;
for (int i = n - 1; i >= 0; --i) {
int index = lower_bound(C.begin(), C.begin() + X, W[i]) - C.begin();
//int index = mylower_bound(C, X, W[i]);
if (index <= X) {
//printf("값 %d 위치 %d\n", W[i], X);
if (cansitend == -2) {
cansitend = X;
cansitbegin = X;
}
else {
cansitbegin = X;
}
X--;
}
}
if (cansitend == -2) return 1000001LL * 1000002LL;
return cansitend * 1000001LL + cansitbegin;
}
#include "vassal.h"
#include <iostream>
#include <vector>
#include <algorithm>
//using namespace std;
std::vector<int> recover[1000001];
int seg[4000004];
void update(int node, int start, int end, int index, int val) {
if (index<start || index>end) return;
if (start == end) {
seg[node] += val;
return;
}
update(node * 2, start, (start + end) / 2, index, val);
update(node * 2 + 1, (start + end) / 2 + 1, end, index, val);
seg[node] = seg[node * 2] + seg[node * 2 + 1];
}
int sumquery(int node, int start, int end, int i, int j) {
if (start > j || end < i) return 0;
if (i <= start && end <= j) return seg[node];
return sumquery(node * 2, start, (start + end) / 2, i, j) + sumquery(node * 2 + 1, (start + end) / 2 + 1, end, i, j);
}
int kthquery(int node, int start, int end, int kth) {
if (start == end) return start;
if (seg[2 * node] >= kth) {
return kthquery(node * 2, start, (start + end) / 2, kth);
}
else return kthquery(node * 2 + 1, (start + end) / 2 + 1, end, kth - seg[node * 2]);
}
void Init(long long B, std::vector<int> C) {
if (B == 1000001LL * 1000002LL) return;
long long start = B % 1000001LL;
long long endw = B / 1000001LL;
sort(C.begin(), C.end());
//cout << "c의 구간" << '\n';
for (int i = start; i <= endw; ++i) {
update(1, 1, 1000000, C[i], 1);
//cout << C[i] << ' ';
recover[C[i]].push_back(i);
}
//cout << '\n';
}
int Maid(int W) {
//cout <<"N : " << N << '\n';
int before = sumquery(1, 1, 1000000, 1, W - 1);
int cnt = sumquery(1, 1, 1000000, W, 1000000);
//cout << W << ' ';
if (cnt == 0) {
//cout << -1 << '\n';
return -1;
}
else {
int ans = kthquery(1, 1, 1000000, before + 1);
//cout << "C에 해당하는 값 " << ans << ' ';
update(1, 1, 1000000, ans, -1);
int index = recover[ans][recover[ans].size() - 1];
recover[ans].pop_back();
//cout << index << '\n';
return index;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
24604 KB |
Correct |
2 |
Correct |
24 ms |
24740 KB |
Correct |
3 |
Correct |
23 ms |
24608 KB |
Correct |
4 |
Correct |
23 ms |
24612 KB |
Correct |
5 |
Correct |
23 ms |
24864 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
128 ms |
36792 KB |
Wrong |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
169 ms |
36792 KB |
B = 51294051294 |
2 |
Partially correct |
279 ms |
39820 KB |
B = 91757091757 |
3 |
Partially correct |
262 ms |
40360 KB |
B = 99999099999 |
4 |
Partially correct |
296 ms |
40404 KB |
B = 99999099999 |
5 |
Partially correct |
298 ms |
40400 KB |
B = 99999099999 |
6 |
Partially correct |
295 ms |
40296 KB |
B = 99999099999 |
7 |
Partially correct |
262 ms |
40408 KB |
B = 99999099999 |
8 |
Partially correct |
186 ms |
34248 KB |
B = 99999099999 |