Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- #define int long long
- using namespace std;
- bool binary(vector <int> blocks, int x, int minimum, int maximum){
- if (blocks.size()==0){
- return 1;
- }
- int l1=0;
- int r1=blocks.size();
- while (r1-l1>1){
- int m1=(l1+r1)/2;
- if (blocks[m1]<=x+minimum){
- l1=m1;
- }
- else{
- r1=m1;
- }
- }
- int l2=0;
- int r2=blocks.size();
- while (r2-l2>1){
- int m2=(l2+r2)/2;
- if (blocks[m2]<=x+maximum){
- l2=m2;
- }
- else{
- r2=m2;
- }
- }
- if (minimum+x==blocks[l1] || maximum+x==blocks[l2]){
- return 0;
- }
- if (l1==l2){
- return 1;
- }
- return 0;
- }
- signed main(){
- int n, m;
- cin>>n>>m;
- string s;
- cin>>s;
- vector <int> blocks;
- vector <int> droids;
- for (int i=0; i<n; i++){
- if (s[i]=='#'){
- blocks.push_back(i);
- }
- if (s[i]=='D'){
- droids.push_back(i);
- }
- }
- string c;
- cin>>c;
- vector <int> d(m);
- for (int i=0; i<m; i++){
- if (c[i]=='L'){
- d[i]=-1;
- }
- if (c[i]=='R'){
- d[i]=1;
- }
- }
- vector <int> prefix(m+1);
- prefix[0]=0;
- for (int i=1; i<=m; i++){
- prefix[i]=prefix[i-1]+d[i-1];
- }
- int minimum=0;
- int maximum=0;
- for (int i=0; i<=m; i++){
- if(prefix[i]<minimum){
- minimum=prefix[i];
- }
- if (prefix[i]>maximum){
- maximum=prefix[i];
- }
- }
- vector <int> answer;
- for (auto x:droids){
- if (x+minimum<0 || x+maximum>=n){
- continue;
- }
- if (binary(blocks, x, minimum, maximum)==1){
- answer.push_back(x+1);
- }
- }
- cout<<answer.size()<<"\n";
- for (auto y:answer){
- cout<<y<<" ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement