Submission #1097213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097213		vjudge1	Rack (eJOI19_rack)	C++17	100 / 100	7 ms	3348 KiB

rack

#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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 60 / 60