|

General

# Author Problem Lang Verdict Time Memory Sent Judged
128826229 Practice:
VVD4
1476D - 8 GNU C++17 Accepted 561 ms 105380 KB 2021-09-14 17:17:05 2021-09-14 17:17:05

→ Source
#include<bits/stdc++.h>
using namespace std;
// #define int long long
// int arr[10000002];

map<int,map<int,map<bool,int>>> mp;

int dfs(int child,int parent,string &s,int moves)
{
if(child>s.size() or child<0)
return 0;

if(mp[child][parent].find(moves)!=mp[child][parent].end())
return mp[child][parent][moves];
int ans=0;
if(parent>child)
{
if((moves==0 and s[child]=='L') or (moves and s[child]=='R') and child>=0)
ans=1+dfs(child-1,child,s,moves^1);
}
else {
if((moves==0 and s[parent]=='R') or (moves and s[parent]=='L') and child<=s.size())
ans=1+dfs(child+1,child,s,moves^1);
}
return mp[child][parent][moves]=ans;
}

void solve(){
mp.clear();
int n;
cin>>n;
string s;
cin>>s;
for(int i=0;i<=n;i++)
{
if(i==0)
{
cout<<dfs(1,0,s,0)+1<<" ";
}
else if(i==n)
{
cout<<dfs(n-1,n,s,0)+1<<" ";
}
else cout<<dfs(i-1,i,s,0)+dfs(i+1,i,s,0)+1<<" ";
}
cout<<endl;
}

signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);

// precal();

int t;
cin>>t;
while(t--)
solve();

}

?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?