Submission #88941

#	Time	Username	Problem	Language	Result	Execution time	Memory
88941		shoemakerjo	Board (CEOI13_board)	C++14	40 / 100	6 ms	2104 KiB

board

#include <bits/stdc++.h>

using namespace std;

string fguy, sguy;

vector<int> fn, sn;
vector<int> fsub, ssub;

void inc(vector<int>& cur) {

	for (int i = cur.size()-1; i >= 0; i--) {
		if (cur[i] == 0) {
			cur[i] = 1;
			break;
		}
		else cur[i] = 0;
	}
}

int getlast(vector<int>& cur) {
	return cur[cur.size()-1];
}


vector<int> subvec(vector<int> a, vector<int> b) {
	//returns a vector, assumes same length

	bool hascarry = false;
	for (int i = a.size()-1; i >= 0; i--) {
		if (hascarry) {
			a[i]--;
			hascarry = false;
		}

		a[i] -= b[i];

		if (a[i] < 0) {
			a[i] += 2;
			hascarry = true;
		}

	}

	return a;


}

int getval(vector<int>& cur) {

	if (cur.size() > 19) {
		return 1000000000;
	}

	int ans = 0;
	for (int i = 0; i < cur.size(); i++) {
		ans *= 2;
		ans += cur[i];
	}
	return ans;
}

string printvect(vector<int>& guy) {

	string res = "";
	for (int i = 0; i < guy.size(); i++) {
		res += to_string(guy[i]);
	}

	return res;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> fguy >> sguy;

	fn.push_back(1);
	sn.push_back(1);

	fsub.push_back(0);
	ssub.push_back(0);

	int ans = 1000000000;


	for (int i = 0; i < fguy.length(); ++i) {
		if (fguy[i] == '1') {
			fn.push_back(0);
			fsub.push_back(0);
		}
		if (fguy[i] == '2') {
			fn.push_back(1);
			fsub.push_back(0);
		}
		if (fguy[i] == 'U') {
			if (getlast(fsub) == 1) {
				if (getlast(fn) != 1) {
					inc(fsub);
				}
			}
			fn.pop_back();
			fsub.pop_back();

		}
		if (fguy[i] == 'L') {
			inc(fsub);
		}
		if (fguy[i] == 'R') {
			inc(fn);
		}
	}
	for (int i = 0; i < sguy.length(); ++i) {
		if (sguy[i] == '1') {
			sn.push_back(0);
			ssub.push_back(0);
		}
		if (sguy[i] == '2') {
			sn.push_back(1);
			ssub.push_back(0);
		}
		if (sguy[i] == 'U') {
			if (getlast(ssub) == 1) {
				if (getlast(sn) != 1) {
					inc(ssub);
				}
			}
			sn.pop_back();
			ssub.pop_back();

		}
		if (sguy[i] == 'L') {
			inc(ssub);
		}
		if (sguy[i] == 'R') {
			inc(sn);
		}
	}

	fn = subvec(fn, fsub);
	sn = subvec(sn, ssub);

	// cout << "fn: " << printvect(fn) << " " << getval(fn) << endl;
	// cout << "sn: " << printvect(sn) << " " << getval(sn) << endl;
	// cout << endl;

	int cans = 0;

	while (fn.size() > sn.size()) {
		fn.pop_back();
		cans++;
	}
	while (sn.size() > fn.size()) {
		sn.pop_back();
		cans++;
	}

	bool sngreater = false;

	for (int i = 0; i < fn.size(); i++) {
		if (fn[i] > sn[i]) break;
		if (sn[i] > fn[i]) {
			sngreater = true;
			break;
		}
	}

	if (sngreater) {
		fn.swap(sn);
	}


	
	int firstdiff = fn.size() + 1;
	for (int i = 0; i < fn.size(); i++) {
		if (fn[i] != sn[i]) {
			firstdiff= i;
			assert(fn[i] > sn[i]);
			break;
		}
	}

	for (int i = fn.size()-1; i >= 0; i--) {
		

		int cdiff = 0;
		if (i >= firstdiff && i - firstdiff <= 19) {

			vector<int> ftemp, stemp;
			for (int j = firstdiff; j <= i; j++) {
				ftemp.push_back(fn[j]);
				stemp.push_back(sn[j]);
				vector<int> ctemp = subvec(ftemp, stemp);
				cdiff = getval(ctemp);

			}
		}
		else if (i >= firstdiff) cdiff = 1000000000;


		// cout << "fn: " << printvect(fn) << " " << getval(fn) << endl;
		// cout << "sn: " << printvect(sn) << " " << getval(sn) << endl;
		// cout << "cdiff: " << cdiff << endl;
		ans = min(ans, cans + cdiff);

		cans += 2;


	}

	cout << ans << endl;


}
//DIFFERENCE IS ALL MESSED UP

Compilation message (stderr)

board.cpp: In function 'int getval(std::vector<int>&)':
board.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < cur.size(); i++) {
                  ~~^~~~~~~~~~~~
board.cpp: In function 'std::__cxx11::string printvect(std::vector<int>&)':
board.cpp:67:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < guy.size(); i++) {
                  ~~^~~~~~~~~~~~
board.cpp: In function 'int main()':
board.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < fguy.length(); ++i) {
                  ~~^~~~~~~~~~~~~~~
board.cpp:115:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < sguy.length(); ++i) {
                  ~~^~~~~~~~~~~~~~~
board.cpp:162:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < fn.size(); i++) {
                  ~~^~~~~~~~~~~
board.cpp:177:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < fn.size(); i++) {
                  ~~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10