# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
55652 | 2018-07-08T11:12:26 Z | leehosu01 | 게임판 (CEOI13_board) | C++17 | 0 ms | 0 KB |
#include<bits/stdc++.h> using namespace std; typedef long long ll; class IB{ public: bitset<101111>NB; int DE; IB(){DE=0;NB.reset();} void operator<<(int n){for(;n--;DE++)NB.reset(DE);} void operator>>(int n){for(;n--;DE--)NB.reset(DE);} void operator++() { int i; for(i=DE-1;i>=0;i--) if(NB.test(i)) NB.reset(i); else break; if(i==-1)NB.set(0),DE++; else NB.set(i); } void operator--() { int i; for(i=DE-1;i>=0;i--) if(!NB.test(i)) NB.set(i); else break; if(i==-1)NB.set(DE),DE++; else NB.reset(i); } bool operator< (const IB&X)const { for(int i=0;i<max(DE,X.DE);i++) if(NB.test(DE-X.DE+i)!=X.NB.test(i)) return X.NB.test(i); return 0; } }tr[2]; ll mi=1<<30; ll pro(int l) { static ll T=0; static int i=0; for(;i<l;i++) { T<<=1; T+=(ll)tr[1].NB.test(i)-tr[0].NB.test(i); } return T; } int main() { ios::sync_with_stdio(0); cin.tie(0); string S; for(int i=0;i<=1;i++) { cin>>S; for(auto&I:S) { if(I=='1')tr[i]<<1; else if(I=='2')tr[i]<<1,++tr[i]; else if(I=='U')tr[i]>>1; else if(I=='L')--tr[i]; else if(I=='R')++tr[i]; } } int i; if(tr[1]<tr[0])swap(tr[0],tr[1]); for(i=0;i<=tr[1].DE;i++) {-0 ll TP=pro(i); mi=min(mi,abs(i-tr[0].DE)+abs(i-tr[1].DE)+TP); if(TP>mi)break; } cout<<mi; }