# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
128826229 |
Practice:
VVD4 |
1476D
- 8
|
C++17 (GCC 7-32)
|
Accepted
|
561 ms
|
105380 KB
|
2021-09-14 17:17:05 |
2021-09-14 17:17:05 |
|
#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();
}
Click to see test details