1722D - Line - CodeForces Solution

greedy

Please click on ads to support us..

Python Code: 

t=int(input())

for i in range(t):
    n= int(input())
    s=input()
    if n==1:
        print(0)
    else:
        
        sum=0
        l=[]
        for i in range(n):
            if s[i]=="L":
                sum+=i
            else:
                sum+=n-1-i
                
        pos1=[]
        pos2=[]
        
        for i in range(n):
            if i<int(n/2):
                if s[i]=="L":
                    pos1.append(i)
            elif i==int(n/2) and n%2==1 :
                pass
            else:
                if s[i]=="R":
                    pos2.append(i)
    
        first=0
        last=len(pos2)-1 
        while first<len(pos1) and last>=0:
            if pos1[first]<= n-1-pos2[last]:
                sum+=  n-1-pos1[first] -pos1[first]
                l.append(sum)
                first+=1

            else:
                sum+= pos2[last] - (n-1-pos2[last])
                l.append(sum)
                last-=1
        
        if first==len(pos1) and last>=0:
            while last>=0:
                sum+= pos2[last] - (n-1-pos2[last])
                l.append(sum)
                last-=1
        
        elif last<0 and first<=len(pos1)-1:
            while first<=len(pos1)-1:
                sum+= n-1-pos1[first]-pos1[first]
                l.append(sum)
                first+=1
        else:
            pass
        
        if len(l)==0:
            l=[sum]*(n-len(l))
        else:
            l=l+ [l[len(l)-1]]*(n-len(l))
        
        print(*l)

C++ Code: 

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int t;
  cin >> t;
  while (t--)
  {
    long long n;
    cin >> n;
    string s;
    cin >> s;
    long long sum = 0;
    int count = 0;
    for (int i = 0; i < s.size(); i++)
    {
      if (s[i] == 'L')
      {
        sum += i;
      }
      else
        sum += (n - i - 1);
    }
    // cout<<sum<<endl;
    vector<long long> v;
    for(int i=0;i<s.size()/2;i++)
    {
      if(s[i]=='L' && i<s.size()/2)
      {
        sum += abs((n - i - 1) - (i));
        v.push_back(sum);
      }
      if(s[n-i-1]=='R' && (n-i-1)>=s.size()/2)
      {
         sum += abs(i - (n - i - 1));
         v.push_back(sum);
      }
      // if(i==s.size()/2 && )
    }


    // for (int i = 0; i < s.size() / 2; i++)
    // {
    //   if (s[i] == 'R')
    //   {
    //     // count++;
    //   }
    //   else
    //   {
    //     sum += (n - i - 1) - (i);
    //     v.push_back(sum);
    //     // cout << sum << " ";
    //   }
    // }

    // for (int i = s.size() / 2; i < n; i++)
    // {
    //   if (i == s.size() / 2 && n % 2 != 0)
    //     continue;
    //   else if (s[i] == 'L')
    //   {
    //     // cout << sum << " ";
    //   }
    //   else
    //   {
    //     sum += i - (n - i - 1);
    //     v.push_back(sum);
    //     // cout << sum << " ";
    //   }
    // }

    if (v.size() != 0)
    {
      sort(v.begin(),v.end());
      for (int i = 0; i < v.size(); i++)
      {
        cout << v[i] << " ";
      }
      for (int i = 0; i < n - v.size(); i++)
      {
        cout << v[v.size() - 1] << " ";
      }
      cout << endl;
    }
    else
    {
      for(int i=0;i<n;i++)
      {
        cout<<sum<<" ";
      }
      cout<<endl;
    }
  }
  return 0;
}


Comments

Submit
0 Comments
More Questions

1002. Find Common Characters
1602A - Two Subsequences
1555A - PizzaForces
1607B - Odd Grasshopper
1084A - The Fair Nut and Elevator
1440B - Sum of Medians
1032A - Kitchen Utensils
1501B - Napoleon Cake
1584B - Coloring Rectangles
1562B - Scenes From a Memory
1521A - Nastia and Nearly Good Numbers
208. Implement Trie
1605B - Reverse Sort
1607C - Minimum Extraction
1604B - XOR Specia-LIS-t
1606B - Update Files
1598B - Groups
1602B - Divine Array
1594B - Special Numbers
1614A - Divan and a Store
2085. Count Common Words With One Occurrence
2089. Find Target Indices After Sorting Array
2090. K Radius Subarray Averages
2091. Removing Minimum and Maximum From Array
6. Zigzag Conversion
1612B - Special Permutation
1481. Least Number of Unique Integers after K Removals
1035. Uncrossed Lines
328. Odd Even Linked List
1219. Path with Maximum Gold