oj.uz

Submission #269337

# Submission time Handle Problem Language Result Execution time Memory
269337 2020-08-17T06:33:50 Z shrek12357 Board (CEOI13_board) C++14
100 / 100
 5 ms 2108 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
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;
 
 
}
 
ll getval(vector<int>& cur) {
 
	if (cur.size() > 19) {
		return 1000000000;
	}
 
	ll ans = 0;
	for (int i = 0; i < cur.size(); i++) {
		ans *= 2LL;
		ans += cur[i] + 0LL;
	}
	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);
 
	ll 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;
 
	ll 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);
	}
 
	ll cdiff = 0LL;
	for (int i = 0; i < fn.size() && cdiff <= 300000; i++) {
 
		cdiff *= 2LL;
		cdiff += fn[i] - sn[i];
 
		ll trav = (fn.size() - i - 1) * 2;
 
		ans = min(ans, trav + cdiff + cans);
	}
 
	cout << ans << endl;
 
 
}

Compilation message

board.cpp: In function 'long long int getval(std::vector<int>&)':
board.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for (int i = 0; i < cur.size(); i++) {
      |                  ~~^~~~~~~~~~~~
board.cpp: In function 'std::string printvect(std::vector<int>&)':
board.cpp:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for (int i = 0; i < guy.size(); i++) {
      |                  ~~^~~~~~~~~~~~
board.cpp: In function 'int main()':
board.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for (int i = 0; i < fguy.length(); ++i) {
      |                  ~~^~~~~~~~~~~~~~~
board.cpp:116:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |  for (int i = 0; i < sguy.length(); ++i) {
      |                  ~~^~~~~~~~~~~~~~~
board.cpp:163:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |  for (int i = 0; i < fn.size(); i++) {
      |                  ~~^~~~~~~~~~~
board.cpp:176:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |  for (int i = 0; i < fn.size() && cdiff <= 300000; i++) {
      |                  ~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 768 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 528 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 416 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 388 KB Output is correct
4 Correct 1 ms 384 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 416 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 392 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2108 KB Output is correct
2 Correct 4 ms 2004 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 640 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2108 KB Output is correct
2 Correct 4 ms 2108 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 4 ms 2108 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1980 KB Output is correct
2 Correct 4 ms 2108 KB Output is correct
3 Correct 3 ms 1920 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 4 ms 2108 KB Output is correct