oj.uz

Submission #117979

# Submission time Handle Problem Language Result Execution time Memory
117979 2019-06-17T15:28:15 Z Adhyyan1252 Board (CEOI13_board) C++11
70 / 100
 200 ms 920 KB 
#include<bits/stdc++.h>

using namespace std;


struct num{
	deque<int> a;
	int dep;
	num(){
		a = {0};
		dep = 0;
	}
	void mult2(){
		a.push_back(0);
	}
	
	void div2(){
		assert(a.size() > 0);
		a.pop_back();
	}
	
	void inc(){
		if(a.size() == 0){
			a.push_back(1); return;
		}
		a.back() += 1;
		int pntr = a.size()-1;
		while(pntr > 0 && a[pntr] > 1){
			a[pntr] = 0;
			a[pntr-1] += 1;
			pntr--;
		}
		if(a[0] > 1){
			a.push_front(1);
			a[1] = 0;
		}
	}
	
	void dec(){
		int pntr = a.size()-1;
		for(; pntr >= 0 && a[pntr] == 0; pntr--);
		assert(a[pntr] == 1);
		a[pntr] = 0;
		for(pntr++; pntr < a.size(); pntr++){
			a[pntr] = 1;
		}
	}
	
	void clearLeadingZero(){
		while(a.size() && a[0] == 0){
			a.pop_front();
		}
	}
	
	void print(){
		for(int i = 0; i < a.size(); i++){
			cout<<a[i];	
		}
		cout<<endl;
	}
};

void SWAP(num& a, num& b){
	swap(a.a, b.a);
	swap(a.dep, b.dep);
}
void move(num& a, char t){
	if(t == '1'){
		a.mult2();
		a.dep++;
	}else if(t == '2'){
		a.mult2();
		a.inc();
		a.dep++;
	}else if(t == 'U'){
		a.div2();
		a.dep--;
	}else if(t == 'L'){
		a.dec();
	}else if(t == 'R'){
		a.inc();
	}else{
		assert(false);
	}
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0);
	num a, b;
	string ainp, binp;
	cin>>ainp>>binp;
	for(int i = 0; i < ainp.length(); i++){
		move(a, ainp[i]);
	}
	for(int i = 0; i < binp.length(); i++){
		move(b, binp[i]);
	}
	
	a.clearLeadingZero();
	b.clearLeadingZero();
	
	
	if(a.dep > b.dep){ //A is closer to the root
		SWAP(a, b);
	}
	int ans = 0;
	while(b.dep > a.dep){
		move(b, 'U');
		ans++;
	}
	
	//now they are at the same level
	assert(a.dep == b.dep);
	
	if(a.a.size() > b.a.size()){ // a has lesser size
		SWAP(a, b);
	}
	while(a.a.size() < b.a.size()){
		a.a.push_front(0);
	}
	a.a.push_front(0);
	b.a.push_front(0);
	assert(a.a.size() == b.a.size());
	
	int lca = 0;
	for(int i = 0; i < a.a.size(); i++){
		if(a.a[i] != b.a[i]){
			lca = i-1;
			break;
		}
	}
	if(a.a == b.a){
		cout<<ans<<endl;
		return 0;
	}
	if(a.a[lca+1] > b.a[lca+1]){ //a is smaller
		SWAP(a, b);
	}
	int dist = 0;
	int bestAns = (a.a.size() - lca + 10)*2;
	
	for(int i = lca; i < a.a.size(); i++){
		dist = dist*2 + (b.a[i] - a.a[i]);
		int curAns = dist + (a.a.size()-i-1)*2;
		if(curAns > 1e7) break;
		bestAns = min(bestAns, curAns);
	}
	
	cout<<bestAns + ans<<endl;
	
}

Compilation message

board.cpp: In member function 'void num::dec()':
board.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(pntr++; pntr < a.size(); pntr++){
               ~~~~~^~~~~~~~~~
board.cpp: In member function 'void num::print()':
board.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < a.size(); i++){
                  ~~^~~~~~~~~~
board.cpp: In function 'int main()':
board.cpp:92:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ainp.length(); i++){
                 ~~^~~~~~~~~~~~~~~
board.cpp:95:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < binp.length(); i++){
                 ~~^~~~~~~~~~~~~~~
board.cpp:126:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.a.size(); i++){
                 ~~^~~~~~~~~~~~
board.cpp:142:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = lca; i < a.a.size(); i++){
                   ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1061 ms 920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 896 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 768 KB Time limit exceeded
2 Halted 0 ms 0 KB -