oj.uz

답안 #1097213

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1097213 2024-10-06T12:28:26 Z vjudge1 Rack (eJOI19_rack) C++17
100 / 100
 7 ms 3348 KB 
#include <iostream>
#include <string>
#include <memory>
#include <algorithm>

// I'd like this to be a different file :(.
namespace HangingRack {

class Solution
{
private:

	// Compute the binary representation of a number of size n.
	static std::string ComputeBinaryRepresenation(long long int k, long long int n)
	{
		std::string answer = "";
		for (int i = n-1; i >= 0; --i)
		{
			if (i > 63)
				answer += '0';
			else
				answer += ((1LL << i)&k) ? '1' : '0';
		}
		return answer;
	}
	
	// Froma given binary string, computes the decimal value modulo.
	static long long int ComputeDecimalNumberModulo(std::string s, long long int modulo)
	{
		long long int answer = 0;
		long long int power_of_2 = 1;
		
		auto FastModuloOperation = [&modulo](long long int x) {
			if (x > modulo)
				return x - modulo;
			return x;
		};
		
		for (int i = s.size()-1; i >= 0; --i)
		{
			if (s[i] == '1')
				answer += power_of_2;
			answer = FastModuloOperation(std::move(answer));
			
			power_of_2 <<= 1;
			power_of_2 = FastModuloOperation(std::move(power_of_2));
		}
		
		return answer;
	}
	
	// Stores the modulo asked.
	long long int const m_modulo = 1'000'000'007LL;
	
	// Depth of the tree.
	long long int m_n;
	
	// Element we want to find.
	long long int m_k;

	// Binary representation of k of size n.
	std::string m_binary_representation_k;
	
	// Store the answer to the problem.
	long long int m_answer;
	
public:
	Solution(std::size_t n, std::size_t k)
	  :  m_n(n),
		 m_k(k)
	{  }
	
	// Solves the problem.
	void Exec()
	{
		m_binary_representation_k = ComputeBinaryRepresenation(m_k, m_n);
		std::string reverse_binary_representation_k = m_binary_representation_k;
		std::reverse(reverse_binary_representation_k.begin(), reverse_binary_representation_k.end());
		m_answer = ComputeDecimalNumberModulo(reverse_binary_representation_k, m_modulo);
	}
	
	// Print the content of the class.
	void Print() const
	{
		std::cout << "n: " << m_n << std::endl;
		std::cout << "k: " << m_k << std::endl;
		std::cout << "binary_representation_k: " << m_binary_representation_k << std::endl;
	}
	
	// Getter for the answer.
	long long int GetAnswer() const { return m_answer; }
};

}

// The "main.cc" file should only contain this.
int main() {
	long long int n, k;
	std::cin >> n >> k;
	std::unique_ptr<HangingRack::Solution> solution = std::make_unique<HangingRack::Solution>(n, k-1);
	solution->Exec();
	std::cout << solution->GetAnswer()+1 << std::endl;
	return 0;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 436 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 436 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 436 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 7 ms 3348 KB Output is correct