QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#698216 | #5078. Castle Design | AMATSUKAZE# | WA | 1ms | 4008kb | C++20 | 3.4kb | 2024-11-01 18:13:31 | 2024-11-01 18:13:32 |
Judging History
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'