fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define mp(a,b)   make_pair(a,b)
  3. #define ll        long long
  4. #define mp(a,b)   make_pair(a,b)
  5. #define si(n)     scanf("%d",&n)
  6. #define sl(n)     scanf("%lld",&n)
  7. #define pi(n)     printf("%d\n",n)
  8. #define pl(n)     printf("%lld\n",n)
  9. #define           newline cout << endl;
  10. #define           ff first
  11. #define           ss second
  12. #define           pii pair<int, int>
  13. #define           pll pair<ll, ll>
  14. using namespace std;
  15.  
  16. template<typename S, typename T> 
  17. ostream& operator<<(ostream& out,pair<S,T> const& p){out<<'('<<p.ff<<", "<<p.ss<<')';return out;}
  18.  
  19. template<typename T>
  20. ostream& operator<<(ostream& out,vector<T> const& v){
  21. int l=v.size();for(int i=0;i<l-1;i++)out<<v[i]<<' ';if(l>0)out<<v[l-1];return out;}
  22.  
  23. template<typename T>
  24. void trace(const char* name, T&& arg1){cout<<name<<" : "<<arg1<<endl;}
  25.  
  26. template<typename T, typename... Args>
  27. void trace(const char* names, T&& arg1, Args&&... args){
  28. const char* comma = strchr(names + 1, ',');cout.write(names, comma-names)<<" : "<<arg1<<" | ";trace(comma+1,args...);}
  29.  
  30. int main(){
  31.   //clock_t tStart = clock();
  32.   int n;
  33.   string s;
  34.   ll endx,endy;
  35.   cin >> n >> s >> endx >> endy;
  36.   ll x=0,y=0;
  37.   int cntl=0,cntr=0,cntu=0,cntd=0;
  38.   for(int i=0;i<n;i++){
  39.     if(s[i]=='U'){
  40.       y++;
  41.       cntu++;
  42.     }
  43.     if(s[i]=='D'){
  44.       y--;
  45.       cntd++;
  46.     }
  47.     if(s[i]=='R'){
  48.       x++;
  49.       cntr++;
  50.     }
  51.     if(s[i]=='L'){
  52.       x--;
  53.       cntl++;
  54.     }
  55.   }
  56.   if(x==endx && y==endy){
  57.     cout << "0\n";
  58.   }
  59.   else{
  60.     char char1,char2;
  61.     ll cnt1=-1,cnt2=-1;
  62.     bool f = 0;
  63.     if(x>endx){
  64.       char1='R';
  65.     }
  66.     else{
  67.       char1='L';
  68.     }
  69.     if(y>endy){
  70.       char2='U';
  71.     }
  72.     else{
  73.       char2='D';
  74.     }
  75.     ll diff1 = abs(x-endx);
  76.     ll diff2 = abs(y-endy);
  77.     if(diff1%2!=0 || diff2%2!=0){
  78.       f=1;
  79.     }
  80.     else{
  81.       cnt1 = diff1/2;
  82.       cnt2 = diff2/2;
  83.     }
  84.     if(char1=='L' && char2=='U'){
  85.       if(cntl<cnt1 || cntu<cnt2){
  86.         f=1;
  87.       }
  88.     }
  89.     else if(char1=='L' && char2=='D'){
  90.       if(cntl<cnt1 || cntd<cnt2){
  91.         f=1;
  92.       }
  93.     }
  94.     else if(char1=='R' && char2=='U'){
  95.       if(cntr<cnt1 || cntu<cnt2){
  96.         f=1;
  97.       }  
  98.     }
  99.     else if(char1=='R' && char2=='D'){
  100.       if(cntr<cnt1 || cntd<cnt2){
  101.         f=1;
  102.       }
  103.     }
  104.  
  105.     if(cnt1==0) char1='X';
  106.     if(cnt2==0) char2='X';
  107.  
  108.  
  109.     if(f==1){
  110.       cout << "-1\n";
  111.       return 0;
  112.     }
  113.     ll start=0,e=0,len=1e18, tc1=0,tc2=0;
  114.     while(start<n){
  115.       for(;e<n;e++){
  116.         if(tc1<cnt1 || tc2<cnt2){
  117.           if(s[e]==char1){
  118.             tc1++;
  119.           }
  120.           if(s[e]==char2){
  121.             tc2++;
  122.           }
  123.         }
  124.         else{
  125.           break;
  126.         }
  127.       }
  128.       if(tc1==cnt1 && tc2==cnt2)
  129.         len = min(len,e-start);
  130.       if(s[start]==char1) tc1--;
  131.       if(s[start]==char2) tc2--;
  132.       start++;
  133.     }
  134.     if(len==1e18) len=-1;
  135.     cout << len << endl;
  136.   }
  137.   //printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
  138.   return 0;
  139. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/caSZ6o
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!