General
 
 
# 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
→ 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
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details