oj.uz

Submission #118021

# Submission time Handle Problem Language Result Execution time Memory
118021 2019-06-17T17:25:11 Z Adhyyan1252 Board (CEOI13_board) C++11
100 / 100
 5 ms 1152 KB 
#include<bits/stdc++.h>

using namespace std;


struct num{
	deque<int> a;
	int dep;
	num(){
		a = {0};
		dep = 0;
		//a.reserve(2e5);
	}
	void mult2(){
		a.push_back(0);
	}
	
	void div2(){
		assert(a.size() > 0);
		a.pop_back();
	}
	
	void incLazy(){
		if(a.size() == 0){
			a.push_back(1); return;
		}
		a.back() += 1;
	}
	
	void decLazy(){
		a.back() -= 1;
	}
	
	void div2Lazy(){
		if(a.back() < 0){
			a[a.size()-2] += (a.back() - 1)/2;
			a.pop_back();
		}else if(a.back() > 1){
			if(a.size()-2 >= 0 )a[a.size()-2] += (a.back())/2;
			else a.push_front(a.back()/2);
			a.pop_back();
		}else{
			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 eval(){
		clearLeadingZero();
		a.push_front(0);
		for(int i = a.size()-1; i > 0; i--){
			if(a[i] < 0){
				//throw this behind
				a[i-1] += ((a[i] - 1)/2);
				a[i] -= 2*((a[i]- 1)/2);
			}else if(a[i] > 1){
				a[i-1] += a[i]/2;
				a[i] -= 2*(a[i]/2);
			}
		}
		assert(a.front() >= 0);
		while(a.front() > 1){
			a.push_front(a.front()/2);
			a[1] -= 2*a[0];
		}
	}
	
	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.incLazy();
		a.dep++;
	}else if(t == 'U'){
		a.div2Lazy();
		a.dep--;
	}else if(t == 'L'){
		a.decLazy();
	}else if(t == 'R'){
		a.incLazy();
	}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.eval();
	b.eval();
	
	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++;
	}
	b.eval();
	//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 > 3e5) break;
		bestAns = min(bestAns, curAns);
	}
	
	cout<<bestAns + ans<<endl;
	
}

Compilation message

board.cpp: In member function 'void num::dec()':
board.cpp:69: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:101: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:137:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ainp.length(); i++){
                 ~~^~~~~~~~~~~~~~~
board.cpp:140:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < binp.length(); i++){
                 ~~^~~~~~~~~~~~~~~
board.cpp:173:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.a.size(); i++){
                 ~~^~~~~~~~~~~~
board.cpp:188: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 4 ms 640 KB Output is correct
2 Correct 3 ms 476 KB Output is correct
3 Correct 4 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 5 ms 768 KB Output is correct
3 Correct 4 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 284 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 432 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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 4 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
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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