oj.uz

Submission #80472

# Submission time Handle Problem Language Result Execution time Memory
80472 2018-10-20T23:09:31 Z Plurm Board (CEOI13_board) C++11
10 / 100
 9 ms 1960 KB 
#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;
	holder& operator=(const holder& y){
		masker = y.masker;
		hasher = y.hasher;
		updt = y.updt;
		return *this;
	}
	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 = masker.size()-1; i > masker.size()-20 && i >= 0; i--){
            if (masker[i] > 1) {
              masker[i-1] += masker[i]/2;
              masker[i] %= 2;
            }
            if (masker[i] < 0) {
              masker[i-1] += (masker[i]-1)/2;
              masker[i] = (masker[i]+1000000007)%2;
            }
		}
	}
	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 + 1);
			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]);
	}
	ma.update();
	for(int i = 0; b[i]; i++){
		mb.move(b[i]);
	}
	mb.update();
	if(ma.length() < mb.length()){
		swap(ma,mb);
	}
	int lla = ma.length();
	int llb = mb.length();
	while(ma.length() > mb.length()){
		ma.move('U');
	}
	int d = lla + llb;
	int cur = 0;
	int rig = 0;
	for(int i = 0; i < mb.length(); i++){
		if(!rig && ma.masker[i] != mb.masker[i]){
			if(ma.masker[i] < mb.masker[i]) rig = 2;
			else rig = 1;
		}
		cur *= 2;
		if(rig == 1) cur += ma.masker[i] - mb.masker[i];
		else cur += mb.masker[i] - ma.masker[i];
		d = min(d,cur + lla - 2*i + llb - 2);
		if(cur > d) break;
	}
	printf("%d\n",d);
	return 0;
}

Compilation message

board.cpp: In member function 'void holder::update()':
board.cpp:32:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = masker.size()-1; i > masker.size()-20 && i >= 0; i--){
                                ~~^~~~~~~~~~~~~~~~~~
board.cpp: In function 'int main()':
board.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",a);
  ~~~~~^~~~~~~~
board.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",b);
  ~~~~~^~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 576 KB Output is correct
2 Incorrect 3 ms 576 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 576 KB Output is correct
2 Incorrect 2 ms 576 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 612 KB Output is correct
2 Incorrect 7 ms 716 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 716 KB Output is correct
2 Incorrect 7 ms 764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1956 KB Output is correct
2 Incorrect 7 ms 1956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1956 KB Output is correct
2 Correct 8 ms 1956 KB Output is correct
3 Correct 2 ms 1956 KB Output is correct
4 Correct 2 ms 1956 KB Output is correct
5 Incorrect 5 ms 1960 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1960 KB Output is correct
2 Incorrect 8 ms 1960 KB Output isn't correct
3 Halted 0 ms 0 KB -