Cod sursa(job #2432989)

Utilizator Mihai7Gheoace Mihai Mihai7 Data 25 iunie 2019 17:05:42
Problema Fractal Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.74 kb
#include <fstream>
#include <vector>

using namespace std;

class Solution {
	int k;
	int x;
	int y;
	int ans;
	vector<int> lastSquare;
 public:
	void readData() {
		ifstream f("fractal.in");
		f >> k >> x >> y;
	}

	/*
	   2^k-1 |
	-------------------
	         |
	*/
	inline int getQuadrant(int x, int y, int half) {
		if (x > half) {
			if (y > half) {
				return 3;
			}
			else {
				return 2;
			}
		} else {
			if (y > half) {
				return 0;
			}
			else {
				return 1;
			}
		}
	}

	inline void perm0(vector<int>& v) {
		swap(v[1], v[3]);
	};

	inline void perm1(vector<int>& v) {
		swap(v[0], v[2]);
	}

	inline void perm2(vector<int>& v) {
		// nothing
	}

	inline void perm3(vector<int>& v) {
		// nothing
	}

	void recursive() {
		int half = 1 << (k - 1);
		if (x > 2 || y > 2) {
			int cad = getQuadrant(x, y, half);
			switch (cad) {
			case 0:
				ans += 3 * (half << 1);
				if (x > 2) {
					x = x - half;  // redundant code to avoid memory jumps
				}
				if (y > 2) {
					y = y - half;
				}
				recursive();
				perm0(lastSquare);
				break;
			case 1:
				// ans += 0 * ...;
				if (x > 2) {
					x = x - half;  // redundant code to avoid memory jumps
				}
				if (y > 2) {
					y = y - half;
				}
				recursive();
				perm1(lastSquare);
				break;
			case 2:
				ans += (half << 1);
				if (x > 2) {
					x = x - half;  // redundant code to avoid memory jumps
				}
				if (y > 2) {
					y = y - half;
				}
				recursive();
				perm2(lastSquare);
				break;
			case 3:
				ans += half << 2;  // 4 * half
				if (x > 2) {
					x = x - half;  // redundant code to avoid memory jumps
				}
				if (y > 2) {
					y = y - half;
				}
				recursive();
				perm3(lastSquare);
				break;
			}
		}
	}

	void getNrSteps() {
		/*
		while(x/2 != 1) {
		sol += 3 | 2 | 1 * pow(2, k);
		}
		sol += 3 | 2 | 1 | 0;
		la final sunt 4 * 4 combinatii se pot micsora?
		*/

		/* lastSquare
		index - quadrant index
		value - value to be added to ans
		*/
		lastSquare.resize(4, 0);
		lastSquare[0] = 3;
		lastSquare[1] = 0;
		lastSquare[2] = 1;
		lastSquare[3] = 2;

		// reduce to the appropiate square
		int half = 1 << (k - 1);
		while (half >= 2 && x < half && y < half) {
			half >>= 1;
			--k;
		}

		recursive();

		/*
		la ordinul 2 gasim ca primul |_| sta doar in doua poziti
		al doilea in doar 
		*/
		/*
		pare ca fiecare poate fi gandi ca o permutare
		*/
		int cad = getQuadrant(x, y, 1);

		ans += lastSquare[cad];
	}

	void printInt() {
		ofstream g("fractal.out");
		g << ans;
	}
};

int main() {
	std::ios_base::sync_with_stdio(false);
	Solution solution;
	solution.readData();
	solution.getNrSteps();
	solution.printInt();
}