oj.uz

Submission #50898

# Submission time Handle Problem Language Result Execution time Memory
50898 2018-06-14T10:37:55 Z tmwilliamlin168 Board (CEOI13_board) C++14
100 / 100
 122 ms 2180 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxD=1e5, bs=62, mxBC=mxD/bs+1;
int sa, sb, ans=2*mxD, a1=0;
ll bva[mxBC], bvb[mxBC];

inline void rd(ll *bv, int &s) {
	bv[0]=1LL<<(bs-1);
	s=1;
	string ms;
	cin >> ms;
	for(char c : ms) {
		if(c=='1') {
			bv[s/bs]&=~(1LL<<(bs-1-s%bs));
			++s;
		} else if(c=='2') {
			bv[s/bs]|=1LL<<(bs-1-s%bs);
			++s;
		} else if(c=='L') {
			bv[(s-1)/bs]-=1LL<<(bs-1-(s-1)%bs);
			for(int i=(s-1)/bs; bv[i]<0; --i) {
				bv[i]+=1LL<<bs;
				--bv[i-1];
			}
		} else if(c=='R') {
			bv[(s-1)/bs]+=1LL<<(bs-1-(s-1)%bs);
			for(int i=(s-1)/bs; bv[i]>=1LL<<bs; --i) {
				bv[i]-=1LL<<bs;
				++bv[i-1];
			}
		} else
			--s;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	rd(bva, sa);
	rd(bvb, sb);
//	cout << bva[0] << " " << bvb[0] << endl;
	for(int i=0; i<min(sa, sb)&&abs(a1)<=ans; ++i) {
		a1=2*a1+(bva[i/bs]>>(bs-1-i%bs)&1)-(bvb[i/bs]>>(bs-1-i%bs)&1);
//		cout << i << " " << a1 << endl;
		ans=min(abs(a1)+sa-i+sb-i-2, ans);
	}
	cout << ans;
}

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 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 880 KB Output is correct
2 Correct 64 ms 1052 KB Output is correct
3 Correct 2 ms 1052 KB Output is correct
4 Correct 2 ms 1052 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1120 KB Output is correct
2 Correct 47 ms 1376 KB Output is correct
3 Correct 2 ms 1376 KB Output is correct
4 Correct 2 ms 1376 KB Output is correct
5 Correct 122 ms 1656 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 1656 KB Output is correct
2 Correct 47 ms 1828 KB Output is correct
3 Correct 26 ms 1860 KB Output is correct
4 Correct 2 ms 1860 KB Output is correct
5 Correct 2 ms 1860 KB Output is correct
6 Correct 121 ms 2180 KB Output is correct