Advertisement
ekzolot

Untitled

Sep 12th, 2022
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.94 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #define int long long
  5. using namespace std;
  6. bool binary(vector <int> blocks, int x, int minimum, int maximum){
  7.     if (blocks.size()==0){
  8.         return 1;
  9.     }
  10.     int l1=0;
  11.     int r1=blocks.size();
  12.     while (r1-l1>1){
  13.         int m1=(l1+r1)/2;
  14.         if (blocks[m1]<=x+minimum){
  15.             l1=m1;
  16.         }
  17.         else{
  18.             r1=m1;
  19.         }
  20.     }
  21.     int l2=0;
  22.     int r2=blocks.size();
  23.     while (r2-l2>1){
  24.         int m2=(l2+r2)/2;
  25.         if (blocks[m2]<=x+maximum){
  26.             l2=m2;
  27.         }
  28.         else{
  29.             r2=m2;
  30.         }
  31.     }
  32.     if (minimum+x==blocks[l1] || maximum+x==blocks[l2]){
  33.         return 0;
  34.     }
  35.     if (l1==l2){
  36.         return 1;
  37.     }
  38.     return 0;
  39. }
  40. signed main(){
  41.     int n, m;
  42.     cin>>n>>m;
  43.     string s;
  44.     cin>>s;
  45.     vector <int> blocks;
  46.     vector <int> droids;
  47.     for (int i=0; i<n; i++){
  48.         if (s[i]=='#'){
  49.             blocks.push_back(i);
  50.         }
  51.         if (s[i]=='D'){
  52.             droids.push_back(i);
  53.         }
  54.     }
  55.     string c;
  56.     cin>>c;
  57.     vector <int> d(m);
  58.     for (int i=0; i<m; i++){
  59.         if (c[i]=='L'){
  60.             d[i]=-1;
  61.         }
  62.         if (c[i]=='R'){
  63.             d[i]=1;
  64.         }
  65.     }
  66.     vector <int> prefix(m+1);
  67.     prefix[0]=0;
  68.     for (int i=1; i<=m; i++){
  69.         prefix[i]=prefix[i-1]+d[i-1];
  70.     }
  71.     int minimum=0;
  72.     int maximum=0;
  73.     for (int i=0; i<=m; i++){
  74.         if(prefix[i]<minimum){
  75.             minimum=prefix[i];
  76.         }
  77.         if (prefix[i]>maximum){
  78.             maximum=prefix[i];
  79.         }
  80.     }
  81.     vector <int> answer;
  82.     for (auto x:droids){
  83.         if (x+minimum<0 || x+maximum>=n){
  84.             continue;
  85.         }
  86.         if (binary(blocks, x, minimum, maximum)==1){
  87.             answer.push_back(x+1);
  88.         }
  89.     }
  90.     cout<<answer.size()<<"\n";
  91.     for (auto y:answer){
  92.         cout<<y<<" ";
  93.     }
  94. }
  95.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement