CSES - Leirikisa 5 - Results
Submission details
Task:bakterije
Sender:eXeP
Submission time:2016-08-02 17:44:38 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
Test results
testverdicttime
#1ACCEPTED0.06 sdetails
#2ACCEPTED0.07 sdetails
#3ACCEPTED0.08 sdetails
#4ACCEPTED0.05 sdetails
#5ACCEPTED0.09 sdetails
#6ACCEPTED0.06 sdetails
#7ACCEPTED0.32 sdetails
#80.44 sdetails
#90.18 sdetails
#10--details
#110.17 sdetails
#120.14 sdetails
#130.10 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:41:20: warning: array subscript has type 'char' [-Wchar-subscripts]
     bd[ba] = tr[fak];
                    ^

Code

#include <bits/stdc++.h>
#define i64 long long
#define u64 unsigned long long
#define i32 int
#define u32 unsigned int
#define pii pair<int, int>
#define pll pair<long long, long long>
#define F first
#define S second
#define ld long double
#define defmod 1000000007
#define mati64(a,b) vector<vector<i64>>(a, vector<i64>(b, 0));
using namespace std;
int fuckme[4][2];
int main(){
cin.sync_with_stdio(0);
cin.tie(0);
int tr[1000];
fuckme[0][0] = -1;
fuckme[1][1] = 1;
fuckme[2][0] = 1;
fuckme[3][1] = -1;
tr['U'] = 0;
tr['R'] = 1;
tr['D'] = 2;
tr['L'] = 3;
int n, m, k; cin >> n >> m >> k;
int x, y; cin >> x >> y;
x--;
y--;
int bi[10], bj[10], bd[10];
string t[5][55];
for(int ba = 0; ba < k; ++ba){
char fak; cin >> bi[ba] >> bj[ba] >> fak;
bi[ba]--;
bj[ba]--;
bd[ba] = tr[fak];
for(int i = 0; i < n; ++i)
cin >> t[ba][i];
}
pair<pii, pii> ne[5][55][55][4];
for(int ba = 0; ba < k; ++ba){
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
for(int di = 0; di < 4; ++di){
int ndi = (di+t[ba][i][j]-'0')%4;
if(i == 0 && ndi == 0)
ndi = 2;
else if(j == 0 && ndi == 3)
ndi = 1;
else if(i == n-1 && ndi == 2)
ndi = 0;
else if(j == m-1 && ndi == 1)
ndi = 3;
pii mv = {i+fuckme[ndi][0], j+fuckme[ndi][1]};
ne[ba][i][j][di] = {mv, {ndi, 0}};
}
}
}
}
vector<int> myy(10, -1), lam(10, -1);
vector<i64> es[10], ss[10];
for(int ba = 0; ba < k; ++ba){
queue<pair<pii, pii>> q;
q.push({{bi[ba], bj[ba]}, {bd[ba], 0}});
bool d1[55][55][4] = {0};
int dis[55][55][4] = {0};
while(!q.empty()){
int i = q.front().F.F, j = q.front().F.S, di = q.front().S.F, d = q.front().S.S;
q.pop();
//cout << "taalla " << i << "," << j << " " << di << " " << d << endl;
if(d1[i][j][di]){
while(es[ba].size() > 0 && es[ba].back() >= dis[i][j][di]){
ss[ba].push_back(es[ba].back());
es[ba].pop_back();
}
lam[ba] = d-dis[i][j][di];
break;
}
d1[i][j][di] = 1;
dis[i][j][di] = d;
if(i == x && j == y)
es[ba].push_back(d);
pair<pii, pii> lul = ne[ba][i][j][di];
lul.S.S = d+1;
q.push(lul);
}
/*
cout << "bakteeri " << ba << " : ";
for(auto f: es[ba])
cout << f << " ";
cout << "syklin koko " << lam[ba] << " ";
cout << "syklissa ";
for(auto f: ss[ba])
cout << f<< " ";
cout << endl;
*/
}
i64 ans = 1LL<<60;
for(int ba = 0; ba < k; ++ba){
for(auto f: es[ba]){
bool ok = true;
for(int ba2 = 0; ba2 < k; ++ba2){
if(ba2 == ba)
continue;
bool ok2 = false;
for(auto ff: es[ba2]){
if(ff == f)
ok2 = true;
}
for(auto ff: ss[ba2]){
if(f-ff >= 0 && (f-ff)%lam[ba2] == 0)
ok2 = true;
}
ok&=ok2;
}
if(ok)
ans = min(ans, f);
}
}
for(auto fff: ss[0]){
for(int i = 0; i < 1000000; ++i){
i64 f = fff+i*lam[0];
//cout << "taalla " << f << endl;
bool ok = true;
for(int ba2 = 1; ba2 < k; ++ba2){
bool ok2 = false;
for(auto ff: es[ba2]){
if(ff == f)
ok2 = true;
}
for(auto ff: ss[ba2]){
if(f-ff >= 0 && (f-ff)%lam[ba2] == 0)
ok2 = true;
}
ok&=ok2;
}
if(ok)
ans = min(ans, f);
}
}
if(ans == 1LL<<60)
cout << -1 << endl;
else
cout << ans+1 << endl;
return 0;
}

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
-1

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
-1

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
-1