QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#698216#5078. Castle DesignAMATSUKAZE#WA 1ms4008kbC++203.4kb2024-11-01 18:13:312024-11-01 18:13:32

Judging History

你现在查看的是最新测评结果

  • [2024-11-01 18:13:32]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4008kb
  • [2024-11-01 18:13:31]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,s,n) for (int i = (int)(s); i < (int)(n); i++)
#define all(v) begin(v),end(v)
using namespace std;
using ll = long long;
using vl=vector<ll>;
using vvl=vector<vl>;
using vvvl=vector<vvl>;
using pll=pair<ll,ll>;
using vp=vector<pll>;
bool chmin(auto &a, auto b){ return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, auto b){ return a < b ? a = b, 1 : 0; }
constexpr ll INF=1LL<<60;
constexpr ll inf=1LL<<30;

int main(){
    cin.tie(0)->sync_with_stdio(0);

    string s;
    cin>>s;
    ll n=s.size();
    s+=s[0];
    ll t=2;
    rep(i,0,n)if(s[i]=='R'&&s[i+1]=='R') t=1;
    if(t==2){
        vl a;
        rep(i,0,n)if(s[i]=='L'&&s[i+1]=='L') a.emplace_back(i);
        assert((ll)a.size()==4);
        vl b(4);
        rep(i,0,4) b[i]=((i==3?a[0]+n:a[i+1])-a[i])>>1;
        ll rs=0;
        rep(i,0,2){
            ll mx=0;
            rep(j,0,2){
                ll sm=1;
                rep(k,0,2) sm+=b[(2*j+k+i)%4];
                chmax(mx,sm);
            }
            rs+=mx;
        }
        rs<<=1;
        cout<<rs<<endl;
    }
    else{
        auto f=[&](ll l,ll r){
            vl b;
            while(1){
                l=(l+2)%n;
                if(l==r) break;
                b.emplace_back(s[l]=='L'?1:-1);
            }
            return b;
        };
        vl b,c;
        rep(i,0,n)if(s[i]=='R'&&s[i+1]=='R'){
            ll x=i+1,y=i+1;
            while(1){
                if(s[x]=='L'&&s[x+1]=='L') break;
                x=(x-2+n)%n;
            }
            while(1){
                if(s[y]=='L'&&s[y+1]=='L') break;
                y=(y+2)%n;
            }
            b=f(x,y),c=f(y,x);
            reverse(all(c));
//            for(auto &v:c) v=-v;
            break;
        }
        if(b.size()<c.size()) swap(b,c);
        ll sb=b.size();
        ll sc=c.size();
        vl ys(sb+1),yu(sc+1);
        {
            ll y=0;
            rep(i,0,sb){
                y+=b[i];
                ys[i+1]=y;
            }
        }{
            ll y=0;
            rep(i,0,sc){
                y+=c[i];
                yu[i+1]=y;
            }
        }
        vl dp(sc+1,INF);
        dp[0]=0;
        rep(I,0,sb+1){
            ll y=ys[I];
            vl DP(sc+1,INF);
            rep(i,0,sc+1)if(dp[i]<INF){
                chmin(DP[i],max(dp[i],y-yu[i]+1));
                if(i<sc){
                    if(I==0) continue;
                    chmin(DP[i+1],max(dp[i],y-yu[i+1]+1));
                }
            }
            dp=DP;
            // rep(j,0,sc+1) cout<<dp[j]<<' ';
            // cout<<endl;
        }
        ll rs=sb+1;
        for(auto v:b)if(v==-1) rs++;
        for(auto v:c)if(v==-1) rs++;
        rs+=dp[sc];
        rs<<=1;
        cout<<rs<<endl;

        // for(auto x:b) cout<<x<<' ';
        // cout<<endl;
        // for(auto x:c) cout<<x<<' ';
        // cout<<endl;
        // auto judge=[&](ll d){
        //     ll y=d,I=0;
        //     for(auto v:c){
        //         y+=v;
        //         while(I<sb+1&&y<=ys[I]) I++;
        //         if(I==sb+1) return false;
        //         I++;
        //     }
        //     return true;
        // };
        // ll l=0,r=1<<30;
        // while(r-l>1){
        //     ll mid=(l+r)/2;
        //     if(judge(mid)) r=mid;
        //     else l=mid;
        // }
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3876kb

input:

LLRLLRLLRLRLLR

output:

16

result:

ok single line: '16'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

RLLRLLLRRLLRLRLL

output:

20

result:

ok single line: '20'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

LLRRLLLLRRLL

output:

16

result:

ok single line: '16'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

RLLRLLRLLRLL

output:

12

result:

ok single line: '12'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3776kb

input:

LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...

output:

199996

result:

ok single line: '199996'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3744kb

input:

LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...

output:

155164

result:

ok single line: '155164'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3664kb

input:

LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...

output:

189748

result:

ok single line: '189748'

Test #8:

score: 0
Accepted
time: 1ms
memory: 4008kb

input:

LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...

output:

137900

result:

ok single line: '137900'

Test #9:

score: -100
Wrong Answer
time: 1ms
memory: 3780kb

input:

LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...

output:

100000

result:

wrong answer 1st lines differ - expected: '100002', found: '100000'