CSES - Leirikisa 5 - Results
Submission details
Task:bakterije
Sender:zxc
Submission time:2016-08-02 17:59:41 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
Test results
testverdicttime
#1ACCEPTED0.05 sdetails
#2ACCEPTED0.05 sdetails
#3ACCEPTED0.06 sdetails
#4ACCEPTED0.05 sdetails
#5ACCEPTED0.05 sdetails
#6ACCEPTED0.06 sdetails
#7ACCEPTED0.06 sdetails
#8--details
#90.43 sdetails
#10--details
#11--details
#120.07 sdetails
#13--details

Compiler report

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

Code

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
int n,m,k;
const int MN = 55;
int d[MN][MN][4];
int t[MN][MN];
vector<int> atTrap[5];
int cycleStart[5];
int 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(int 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(int i = 2; i-2 < (int)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(int x) {
if(x == k) {
set<int> beforeCycle;
vector<pair<ll, ll> > q; //atTrap, cycle length
for(int 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(int 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;
int x,y;
cin>>y>>x;
--x, --y;
for(int i = 0; i < k; ++i) {
int px, py;
char c;
cin>>py>>px>>c;
--px, --py;
int dir = 0;
if(c == 'U') dir = 0;
if(c == 'L') dir = 3;
if(c == 'D') dir = 2;
if(c == 'R') dir = 1;
for(int j = 0; j < n; ++j) {
for(int k = 0; k < m; ++k) {
char q;
cin>>q;
t[j][k] = q-'0';
}
}
memset(d, -1, sizeof d);
int 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;
int qx = px;
int 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(int 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 details

Test 1

Verdict: ACCEPTED

input
3 3 1
2 2
1 1 R
010
000
...

correct output
3

user output
3

Test 2

Verdict: ACCEPTED

input
3 4 2
2 2
3 4 R
2327
6009
...

correct output
8

user output
8

Test 3

Verdict: ACCEPTED

input
4 4 3
4 3
1 1 U
1001
0240
...

correct output
296

user output
296

Test 4

Verdict: ACCEPTED

input
10 10 2
2 2
10 10 D
3000000003
3240082600
...

correct output
31

user output
31

Test 5

Verdict: ACCEPTED

input
20 20 3
18 8
18 14 L
52076326768887743424
30953273223516230377
...

correct output
127365

user output
127365

Test 6

Verdict: ACCEPTED

input
16 24 3
1 1
9 15 L
386703035230234125771793
410163209210321990377031
...

correct output
-1

user output
-1

Test 7

Verdict: ACCEPTED

input
35 39 4
11 23
35 10 D
534119390852214853015480726815...

correct output
68430452

user output
68430452

Test 8

Verdict:

input
21 32 5
3 5
15 8 R
334126231002222122244321129954...

correct output
1959913839402

user output
(empty)

Test 9

Verdict:

input
29 44 5
20 21
3 26 L
760376683503757740684647181292...

correct output
62013683483

user output
-1

Test 10

Verdict:

input
40 40 5
28 23
15 9 L
137103427205590752679014023441...

correct output
57788077454

user output
(empty)

Test 11

Verdict:

input
45 49 5
12 15
34 30 R
860736165053314133032790918044...

correct output
10477495826046

user output
(empty)

Test 12

Verdict:

input
47 49 5
17 26
8 40 R
384608891563515730952391281457...

correct output
781942227216

user output
-1

Test 13

Verdict:

input
50 50 5
4 35
27 43 L
998166911112259286230836653527...

correct output
9298781157357368

user output
(empty)