oj.uz

Submission #150559

# Submission time Handle Problem Language Result Execution time Memory
150559 2019-09-01T08:38:38 Z 20190901(#3597, tongnamuu, jf297, upple1) King of Chairs (FXCUP4_chairs) C++17
38 / 100
 316 ms 40404 KB 
#include "king.h"
#include <algorithm>
#include <stdio.h>
int mylower_bound(std::vector<int>& c, int n, int val) {
	int start = 0, end = n;
	while (start <= end) {
		int mid = (start + end) / 2;
		if (c[mid] < val) start = mid + 1;
		else end = mid - 1;
	}
	return start;
}
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 = 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;
	}
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24604 KB Correct
2 Correct 25 ms 24728 KB Correct
3 Correct 25 ms 24864 KB Correct
4 Correct 24 ms 24864 KB Correct
5 Correct 24 ms 24732 KB Correct

Subtask #2
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 36800 KB Wrong
2 Halted 0 ms 0 KB -

Subtask #3
21.0 / 45.0

# Verdict Execution time Memory Grader output
1 Partially correct 184 ms 36688 KB B = 51294051598
2 Partially correct 285 ms 39728 KB B = 91757092109
3 Partially correct 231 ms 36564 KB B = 99999150152
4 Partially correct 316 ms 40400 KB B = 99999100149
5 Partially correct 298 ms 39892 KB B = 99999100401
6 Partially correct 308 ms 40404 KB B = 99999100253
7 Partially correct 228 ms 36548 KB B = 99999150089
8 Partially correct 157 ms 29260 KB B = 1000003000002