oj.uz

Submission #80461

# Submission time Handle Problem Language Result Execution time Memory
80461 2018-10-20T22:24:00 Z Plurm Board (CEOI13_board) C++11
40 / 100
 27 ms 3072 KB 
    #include <bits/stdc++.h>
    using namespace std;
    char a[100005];
    char b[100005];
    class holder{
    public:
    	vector<int> masker;
    	vector<long long> hasher;
    	bool updt = false;
    	int length(){
    		return masker.size();
    	}
    	long long 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] ? 269ll : 732ll;
    			else hasher[i] = 53ll*hasher[i-1] + (long long)(masker[i] ? 269 : 732);
    		}
    	}
    	void move(char x){
    		switch(x){
    		case '1':
    			if(updt) update();
    			masker.push_back(0);
    			hasher.push_back(hasher.empty() ? 732ll : hasher.back()*53ll + 732ll);
    			break;
    		case '2':
    			if(updt) update();
    			masker.push_back(1);
    			hasher.push_back(hasher.empty() ? 269ll : hasher.back()*53ll + 269ll);
    			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;
    		}
    	}
    };
    long long 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() > 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

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

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 456 KB Output is correct
2 Correct 4 ms 456 KB Output is correct
3 Correct 10 ms 584 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 608 KB Output is correct
2 Correct 19 ms 788 KB Output is correct
3 Correct 10 ms 788 KB Output is correct
4 Correct 2 ms 788 KB Output is correct
5 Correct 2 ms 788 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 788 KB Output is correct
2 Correct 21 ms 844 KB Output is correct
3 Correct 10 ms 844 KB Output is correct
4 Incorrect 2 ms 844 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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