oj.uz

Submission #231178

# Submission time Handle Problem Language Result Execution time Memory
231178 2020-05-13T02:07:32 Z thebes Board (CEOI13_board) C++14
100 / 100
 160 ms 8440 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 6392 KB Output is correct
2 Correct 20 ms 6016 KB Output is correct
3 Correct 53 ms 6272 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6016 KB Output is correct
2 Correct 75 ms 6400 KB Output is correct
3 Correct 53 ms 6264 KB Output is correct
4 Correct 9 ms 6016 KB Output is correct
5 Correct 9 ms 5888 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5888 KB Output is correct
2 Correct 9 ms 6016 KB Output is correct
3 Correct 10 ms 6016 KB Output is correct
4 Correct 9 ms 6144 KB Output is correct
5 Correct 9 ms 5888 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6016 KB Output is correct
2 Correct 15 ms 6016 KB Output is correct
3 Correct 9 ms 5992 KB Output is correct
4 Correct 9 ms 6016 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6144 KB Output is correct
2 Correct 74 ms 6400 KB Output is correct
3 Correct 47 ms 6264 KB Output is correct
4 Correct 9 ms 5888 KB Output is correct
5 Correct 9 ms 6016 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 8312 KB Output is correct
2 Correct 139 ms 8312 KB Output is correct
3 Correct 17 ms 6400 KB Output is correct
4 Correct 18 ms 6272 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 8312 KB Output is correct
2 Correct 138 ms 8312 KB Output is correct
3 Correct 14 ms 6144 KB Output is correct
4 Correct 15 ms 6272 KB Output is correct
5 Correct 142 ms 8440 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 8312 KB Output is correct
2 Correct 145 ms 8312 KB Output is correct
3 Correct 81 ms 8056 KB Output is correct
4 Correct 21 ms 6656 KB Output is correct
5 Correct 21 ms 6528 KB Output is correct
6 Correct 160 ms 8440 KB Output is correct