Submission #231178

#	Time	Username	Problem	Language	Result	Execution time	Memory
231178		thebes	Board (CEOI13_board)	C++14	100 / 100	160 ms	8440 KiB

board

#include <bits/stdc++.h>
#define DEBUG 1
using namespace std;

namespace output{
    void __(short x){cout<<x;}
    void __(unsigned x){cout<<x;}
    void __(int x){cout<<x;}
    void __(long long x){cout<<x;}
    void __(unsigned long long x){cout<<x;}
    void __(double x){cout<<x;}
    void __(long double x){cout<<x;}
    void __(char x){cout<<x;}
    void __(const char*x){cout<<x;}
    void __(const string&x){cout<<x;}
    void __(bool x){cout<<(x?"true":"false");}
    template<class S,class T>
    void __(const pair<S,T>&x){__(DEBUG?"(":""),__(x.first),__(DEBUG?", ":" "),__(x.second),__(DEBUG?")":"");}
    template<class T>
    void __(const vector<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class T>
    void __(const set<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class T>
    void __(const multiset<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class S,class T>
    void __(const map<S,T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    void pr(){cout<<"\n";}
    template<class S,class... T>
    void pr(const S&a,const T&...b){__(a);if(sizeof...(b))__(' ');pr(b...);}
}

using namespace output;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,char> pic;
typedef pair<double,double> pdd;
typedef pair<ld,ld> pld;
typedef vector<int> vi;
typedef vector<ll> vl;

#define pb push_back
#define fox(i,x,y) for(int i=(x);i<=(y);i++)
#define foxr(i,x,y) for(int i=(y);i>=(x);i--)
#define F first
#define S second

const int MN = 1e5+5, mod = 1e9+7;
int pw[MN]={1}, one[MN];
struct segtree{
    pii st[3*MN]; int h[3*MN], lz[3*MN];
    int n=100000;
    void init(){
        memset(lz,-1,sizeof(lz));
    }
    inline void upd_lz(int i,int s,int e){
        if(lz[i]!=-1){
            st[i].F=st[i].S=lz[i];
            h[i]=lz[i]?one[e-s+1]:0;
            if(s!=e) lz[2*i]=lz[2*i+1]=lz[i];
            lz[i]=-1;
        }
    }
    void upd(int i,int s,int e,int ss,int se,int val){
        upd_lz(i,s,e);
        if(s>=ss&&e<=se) lz[i]=val, upd_lz(i,s,e);
        else{
            if((s+e)/2<ss) upd(2*i+1,(s+e)/2+1,e,ss,se,val),upd_lz(2*i,s,(s+e)/2);
            else if((s+e)/2>=se) upd(2*i,s,(s+e)/2,ss,se,val),upd_lz(2*i+1,(s+e)/2+1,e);
            else upd(2*i,s,(s+e)/2,ss,se,val),upd(2*i+1,(s+e)/2+1,e,ss,se,val);
            st[i].F=min(st[2*i].F,st[2*i+1].F);
            st[i].S=max(st[2*i].S,st[2*i+1].S);
            h[i]=(1LL*h[2*i]*pw[e-(s+e)/2]+h[2*i+1])%mod;
        }
    }
    inline void upd(int s,int e,int val){
        if(s>e) return;
        upd(1,1,n,s,e,val);
    }
    int qu(int i,int s,int e,int se,int val){
        upd_lz(i,s,e);
        if(s>se||(st[i].F!=val&&st[i].S!=val)) return -1;
        else if(s==e) return s;
        int res=qu(2*i+1,(s+e)/2+1,e,se,val);
        if(res!=-1) return res;
        else return qu(2*i,s,(s+e)/2,se,val);
    }
    inline int query(int dep,int val){
        return qu(1,1,n,dep,val);
    }
    int qu2(int i,int s,int e,int ed){
        upd_lz(i,s,e);
        if(e<=ed) return h[i];
        else if((s+e)/2>=ed) return qu2(2*i,s,(s+e)/2,ed);
        else{
            int l=qu2(2*i,s,(s+e)/2,ed), r=qu2(2*i+1,(s+e)/2+1,e,ed);
            return (1LL*l*pw[ed-(s+e)/2]+r)%mod;
        }
    }
    int get(int dep){
        return qu2(1,1,n,dep);
    }
    inline bool step(int dep,int dir){
        if(dir==0){
            int idx=query(dep,1);
            if(idx==-1) return 0;
            upd(idx,idx,0);
            upd(idx+1,dep,1);
        }
        else{
            int idx=query(dep,0);
            if(idx==-1) return 0;
            upd(idx,idx,1);
            upd(idx+1,dep,0);
        }
        return 1;
    }
    int qu3(int i,int s,int e,int idx){
        upd_lz(i,s,e);
        if(s==e) return st[i].F;
        else if((s+e)/2<idx) return qu3(2*i+1,(s+e)/2+1,e,idx);
        else return qu3(2*i,s,(s+e)/2,idx);
    }
    inline int elem(int idx){
        return qu3(1,1,n,idx);
    }
}A,B;

int n, m, i, j, a, b;
string s, t;

int main(){
    cin >> s >> t;
    for(i=1;i<MN;i++)
        pw[i]=(pw[i-1]*133LL)%mod;
    for(i=1;i<MN;i++)
        one[i]=(one[i-1]*133LL+1)%mod;
    n = s.size(); m = t.size();
    for(auto c : s){
        if(c=='1') a++,A.upd(a,a,0);
        else if(c=='2') a++,A.upd(a,a,1);
        else if(c=='U') a--;
        else if(c=='L') A.step(a,0);
        else if(c=='R') A.step(a,1);
    }
    for(auto c : t){
        if(c=='1') b++,B.upd(b,b,0);
        else if(c=='2') b++,B.upd(b,b,1);
        else if(c=='U') b--;
        else if(c=='L') B.step(b,0);
        else if(c=='R') B.step(b,1);
    }
    ll ans=1LL<<30, dis=0, aa=0, bb=0;
    ll c=a, d=b;
    while(c||d){
        if(c==d&&A.get(c)==B.get(d)) break;
        if(c<d) d--,dis++;
        else c--,dis++;
    }
    int sketchy=0;
    for(i=0;i<=min(a,b)-c&&sketchy<30;i++){
        ans=min(ans,dis+abs(aa-bb));
        aa=(2LL*aa+A.elem(c+i+1))%mod;
        bb=(2LL*bb+B.elem(c+i+1))%mod;
        if(abs(aa-bb)>1) sketchy++;
        dis-=2;
    }
    printf("%lld\n",ans);
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10