Submission #117983

#	Time	Username	Problem	Language	Result	Execution time	Memory
117983		Adhyyan1252	Board (CEOI13_board)	C++11	0 / 100	11 ms	768 KiB

board

#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(){
	
	num A; 
	int TEST = 1e5;
	for(int i = 0; i < TEST; i++){
		A.mult2();
		if(rand()%2) A.inc();
	}
	for(int i = 0; i < TEST; i++){
		A.dec();
	}
	//A.print();
	return 0;
	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;
	assert(false);
	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 (stderr)

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:104:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ainp.length(); i++){
                 ~~^~~~~~~~~~~~~~~
board.cpp:107:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < binp.length(); i++){
                 ~~^~~~~~~~~~~~~~~
board.cpp:138:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.a.size(); i++){
                 ~~^~~~~~~~~~~~
board.cpp:154:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = lca; i < a.a.size(); i++){
                   ~~^~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 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