bakterije

input/code.cpp: In function 'void f(ll)':
input/code.cpp:123:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i = 0; i < atTrap[x].size(); ++i) {
                                      ^

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
ll n,m,k;
const ll MN = 55;
ll d[MN][MN][4];
ll t[MN][MN];
vector<ll> atTrap[5];
ll cycleStart[5];
ll cycleLen[4];
ll ans = 1e18;
ll selected[5];
pair<ll, ll> eu(ll p1, ll p2) {
    vector<pair<ll, ll> > p;
    p.push_back({1, 0});
    p.push_back({0, 1});
    vector<ll> a;
    ll q1 = p1;
    ll q2 = p2;
    for(ll i = 0; ; ++i) {
	if(q1 == 1) break;
	a.push_back(q1/q2);
	//cout<<a.back()<<'\n';
	ll r = q1%q2;
	q1 = q2;
	q2 = r;
    }
    for(ll i = 2; i-2 < (ll)a.size()-1; ++i) {
	pair<ll, ll> z = {-a[i-2]*p[i-1].F, -a[i-2]*p[i-1].S};
	z.F += p[i-2].F;
	z.S += p[i-2].S;
	//cout<<z.F<<' '<<z.S<<'\n';
	if(z.F == 0 && z.S == 0) break;;
	p.push_back(z);
    }
    return p.back();
}
void f2(vector<pair<ll, ll> > q, ll qwe) {
    if(q.size() == 1) {
	//cerr<<"zzz "<<q[0].F<<'\n';
	if(qwe != -1 && q[0].F != qwe) return;
	ans = min(ans, q[0].F);
	return;
    }
    else {
	//cout<<"UUSi\n";
	ll p1 = q.back().S;
	ll t1 = q.back().F;
	q.pop_back();
	ll p2 = q.back().S;
	ll t2 = q.back().F;
	q.pop_back();
	ll gcd = __gcd(p1, p2);
	ll p11 = p1;
	ll p22 = p2;
	p1 /= gcd;
	p2 /= gcd;
	if(t1 == t2) {
	    f2(q, p11*p22/gcd);
	    return;
	}
	if((t2-t1)%gcd) {
	    return;
	}
	ll z = t2-t1;
	pair<ll, ll> y; 
	if(p1 == p2) {
	    y.F = 1;
	    y.S = -1;
	}
	else y= eu(p1, p2);
	y.S = -y.S; //p1*x-p2*y
	y.F *= z/gcd;
	y.S *= z/gcd;
	if(p1*y.F - p2*y.S != z/gcd) {
	    y.F = -y.F;
	    y.S = -y.S;
	}
	while(y.F > 0 && y.S > 0) {
	    y.F -= p2;
	    y.S -= p1;
	}
	while(y.F < 0 || y.S < 0) {
	    y.F += p2;
	    y.S += p1;
	}
	y.F *= gcd;
	y.S *= gcd;
	q.push_back({t1+p1*y.F, p11*p22/gcd});

	f2(q, qwe);
    }
}
void f(ll x) {
    if(x == k) {
	set<ll> beforeCycle;
	vector<pair<ll, ll> > q; //atTrap, cycle length
	for(ll i = 0; i < k; ++i) {
	    if(selected[i] < cycleStart[i]) beforeCycle.insert(selected[i]);
	    else {
		q.push_back({selected[i], cycleLen[i]});
	    }
	}
	if(beforeCycle.size() > 1) {
	    return;
	}
	if(beforeCycle.size() == 0) {
	    //cerr<<"lol\n";
	    f2(q, -1);
	    //cout<<ans<<'\n';
	}
	else {
	    if(q.size() == 0) {
		ans = min(ans, (ll)*beforeCycle.rbegin());
		cerr<<"asd\n";
	    }
	    f2(q, *beforeCycle.begin());
	}
	return;
    }
    for(ll i = 0; i < atTrap[x].size(); ++i) {
	selected[x] = atTrap[x][i];
	f(x+1);
    }
}
int main() {
    //auto z = eu(1211, 107);
   // cout<<z.F<<' '<<z.S<<'\n';
    //return 0;
    cin>>n>>m>>k;
    ll x,y;
    cin>>y>>x;
    --x, --y;
    for(ll i = 0; i < k; ++i) {
	ll px, py;
	char c;
	cin>>py>>px>>c;
	--px, --py;
	ll dir = 0;
	if(c == 'U') dir = 0;
	if(c == 'L') dir = 3;
	if(c == 'D') dir = 2;
	if(c == 'R') dir = 1;
	for(ll j = 0; j < n; ++j) {
	    for(ll k = 0; k < m; ++k) {
		char q;
		cin>>q;
		t[j][k] = q-'0';
	    }
	}
	memset(d, -1, sizeof d);
	ll time = 0;
	while(1) {
	    if(py == y && px == x) {
		atTrap[i].push_back(time);
	    }
	    time++;
	    //cout<<py<<' '<<px<<' '<<y<<' '<<x<<'\n';
	    dir += t[py][px];
	    dir %= 4;
	    ll qx = px;
	    ll qy = py;
	    if(dir == 0) --py;
	    if(dir == 1) ++px;
	    if(dir == 2) ++py;
	    if(dir == 3) --px;
	    if(py == n) {
		py -= 2;
		dir += 2;
	    }
	    if(py == -1) {
		py = 1;
		dir += 2;
	    }
	    if(px == m) {
		px -= 2;
		dir += 2;
	    }
	    if(px == -1) {
		px = 1;
		dir += 2;
	    }
	    dir %= 4;
	    //cout<<qy<<' '<<qx<<' '<<dir<<' '<<time<<'\n';
	    if(d[qy][qx][dir] != -1) {
		cycleStart[i] = d[qy][qx][dir];
		cycleLen[i] = time - d[qy][qx][dir];
		break;
	    }
	    d[qy][qx][dir] = time;
	}
	/*
	cout<<"LOL\n";
	cout<<cycleStart[i]<<' '<<cycleLen[i]<<'\n';
	for(ll j = 0; j < atTrap[i].size(); ++j) {
	    cout<<atTrap[i][j]<<'\n';
	}
	*/
    }
    f(0);
    if(ans != 1e18) cout<<ans+1<<'\n';
    else cout<<-1<<'\n';
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: TIME LIMIT EXCEEDED

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: TIME LIMIT EXCEEDED