Submission #80455

#	Time	Username	Problem	Language	Result	Execution time	Memory
80455		Plurm	Board (CEOI13_board)	C++11	40 / 100	23 ms	2088 KiB

board

#include <bits/stdc++.h>
using namespace std;
char a[100005];
char b[100005];
class holder{
public:
	vector<int> masker;
	vector<int> hasher;
	bool updt = false;
	int length(){
		return masker.size();
	}
	int ghash(){
		return hasher.size() > 20 ? hasher[(int)hasher.size()-20] : -1;
	}
	int gint(){
		int ret = 0;
		for(int i = max((int)masker.size()-19,0); i < (int)masker.size(); i++){
			ret *= 2;
			ret += (int)masker[i];
		}
		return ret;
	}
	void update(){
		updt = false;
		for(int i = 1; i < 20 && (int)masker.size() - i - 1 >= 0; i++){
			if(masker[(int)masker.size() - i - 1]){
				masker.back() += 1 << i;
				masker[(int)masker.size() - i - 1] = 0;
			}
		}
		for(int i = 0; i < 20 && (int)masker.size() - i - 1 >= 0; i++){
			if(masker.back() & (1 << i)){
				masker[(int)masker.size() - i - 1]++;
				masker.back() -= 1 << i;
			}
		}
		for(int i = 0; i < 20 && (int)masker.size() - i - 1 >= 0; i++){
			if(masker[(int)masker.size() - i - 1] > 1){
				masker[(int)masker.size() - i - 1] -= 2;
				if((int)masker.size() - i - 2 >= 0) masker[(int)masker.size() - i - 2]++;
			}
		}
		for(int i = max(0,(int)masker.size() - 20); i < (int)masker.size(); i++){
			if(i == 0) hasher[i] = masker[i]+1;
			else hasher[i] = 53*hasher[i-1] + masker[i]+1;
		}
	}
	void move(char x){
		switch(x){
		case '1':
			if(updt) update();
			masker.push_back(0);
			hasher.push_back(hasher.empty() ? 1 : hasher.back()*53 + 1);
			break;
		case '2':
			if(updt) update();
			masker.push_back(1);
			hasher.push_back(hasher.empty() ? 2 : hasher.back()*53 + 2);
			break;
		case 'U':
			if(updt) update();
			masker.pop_back();
			hasher.pop_back();
			break;
		case 'L':
			masker.back()--;
			updt = true;
			break;
		case 'R':
			masker.back()++;
			updt = true;
			break;
		}
	}
};
int hsh[100005];
int mem[100005];
int main(){
	scanf("%s",a);
	scanf("%s",b);
	holder ma,mb;
	for(int i = 0; a[i]; i++){
		ma.move(a[i]);
	}
	for(int i = 0; b[i]; i++){
		mb.move(b[i]);
	}
	if(ma.length() < mb.length()){
		swap(ma,mb);
	}
	int lla = ma.length();
	int llb = mb.length();
	while(ma.length() > 0){
		hsh[ma.length()] = ma.ghash();
		mem[ma.length()] = ma.gint();
		ma.move('U');
	}
	int d = 1e9;
	while(mb.length() > 0){
		if(hsh[mb.length()] && hsh[mb.length()] == mb.ghash()){
			d = min(d,abs(mem[mb.length()] - mb.gint()) + lla - mb.length() + llb - mb.length());
		}
		mb.move('U');
	}
	printf("%d\n",d);
	return 0;
}

Compilation message (stderr)

board.cpp: In function 'int main()':
board.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",a);
  ~~~~~^~~~~~~~
board.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",b);
  ~~~~~^~~~~~~~

• 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