oj.uz

Submission #151037

# Submission time Handle Problem Language Result Execution time Memory
151037 2019-09-01T15:20:42 Z baikdohyup King of Chairs (FXCUP4_chairs) C++17
100 / 100
 263 ms 10044 KB 
#include "king.h"

long long SendInfo(std::vector<int> W, std::vector<int> C) {
	return 0;
}


#include "vassal.h"
#include <algorithm>
#include <iostream>

std::vector<std::pair<int, int>> chair; // chair weight, order of chair
std::vector<std::pair<int, int>> num; // chair total, chair remain

void Init(long long B, std::vector<int> C){
	int N = C.size();

	for (int i = 0; i < N; i++) {
		if (!chair.empty() && chair.back().first == C[i]) {
			num.back().first++, num.back().second++;
		}
		else {
			chair.push_back(std::pair<int, int>(C[i], i));
			num.push_back(std::pair<int, int>(1, 1));
		}
	}
}

int findidx(int first, int last, int weight, int cut) {
	int mid;

	while (first <= last) {
		mid = (first + last) / 2;
		
		if (mid != cut && chair[mid - 1].first < weight && chair[mid].first >= weight) {
			return mid;
		}
		else if (chair[mid].first < weight) {
			first = mid + 1;
		}
		else if (chair[mid].first >= weight && mid == cut) {
			return mid;
		}
		else {
			last = mid - 1;
		}
	}

	return -1;
}

int Maid(int W){
	int first = 0, last = (int)chair.size() - 1;
	int idx;

	while (1) {
		idx = findidx(first, last, W, first);

		if (idx == -1) {
			return -1;
		}

		if (num[idx].second > 0) {
			int index = chair[idx].second + (num[idx].first - num[idx].second);
			num[idx].second--;

			return index;
		}
		else {
			for (int i = idx + 1; i < (int)chair.size(); i++) {
				if (num[i].second > 0) {
					int index = chair[i].second + (num[i].first - num[i].second);
					num[i].second--;

					return index;
				}
			}

			return -1;
		}
	}

	return -1;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 760 KB Correct
2 Correct 4 ms 632 KB Correct
3 Correct 4 ms 632 KB Correct
4 Correct 4 ms 632 KB Correct
5 Correct 4 ms 1012 KB Correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4136 KB Correct
2 Correct 94 ms 6808 KB Correct
3 Correct 238 ms 9968 KB Correct
4 Correct 92 ms 9812 KB Correct
5 Correct 100 ms 9948 KB Correct
6 Correct 101 ms 9816 KB Correct
7 Correct 247 ms 10012 KB Correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 4168 KB Correct
2 Correct 111 ms 6688 KB Correct
3 Correct 263 ms 9984 KB Correct
4 Correct 118 ms 9860 KB Correct
5 Correct 129 ms 9860 KB Correct
6 Correct 107 ms 9996 KB Correct
7 Correct 260 ms 10044 KB Correct
8 Correct 81 ms 9828 KB Correct