Source Code
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vl;
typedef pair<ll, ll> pl;
typedef long double ld;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define max(a, b) (a>b ? a : b)
#define min(a, b) (a<b ? a : b)
#define FAST ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)


const int N = int(1e6) + 3;
const int MOD = int(1e9) + 7;

string s;
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
int n;
int x[N],y[N];
int val[N];
int xs=0, ys=0;
map<pair<int,int> ,int> maa[4];
int main() {
    FAST;
    //freopen("easy", "r", stdin);
    cin >> s;
    n = s.size();
    for(int i=0;i<n;i++){
        if(s[i]=='U'){
            val[i]=0;
        }else if(s[i]=='D'){
            val[i]=1;
        }else if(s[i]=='L'){
            val[i]=2;
        }else{
            val[i]=3;
        }
        x[i]=xs;
        y[i]=ys;
        xs+=dx[val[i]];
        ys+=dy[val[i]];
    }
    int X = xs;
    int Y = ys;
    ll ans=1e18;
    if(X==0 && Y==0){
        ans=min( ans,n);
    }
    for(int i=0;i<2*n;i++){
        int xx = x[i%n];
        int yy = y[i%n];
        if(i>=n){
            xx+=X;
            yy+=Y;
        }
        if(val[i%n]==0)
           // cout <<val[i%n] <<" "<<i<< " "<< xx << " " << yy << endl;
        if(maa[val[i%n]].count({xx,yy})!=0){
            ans=min(ans,i+1);
        }
        maa[val[i%n]][{xx,yy}]=i+1;
    }
    if(ans<1e18){
        cout << ans;
    }else{
        cout << -1;
    }
    return 0;
}
Copy
Are We There Yet? Mtaylor
GNU G++17
0 ms
520 KB
Wrong Answer