Submission #1097213

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1097213	2024-10-06T12:28:26 Z	vjudge1	Rack (eJOI19_rack)	C++17	100 / 100	7 ms	3348 KB

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.0 / 20.0

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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