Task: | bakterije |
Sender: | zxc |
Submission time: | 2016-08-02 17:59:41 +0300 |
Language: | C++ |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.05 s | details |
#2 | ACCEPTED | 0.05 s | details |
#3 | ACCEPTED | 0.06 s | details |
#4 | ACCEPTED | 0.05 s | details |
#5 | ACCEPTED | 0.05 s | details |
#6 | ACCEPTED | 0.06 s | details |
#7 | ACCEPTED | 0.06 s | details |
#8 | TIME LIMIT EXCEEDED | -- | details |
#9 | WRONG ANSWER | 0.43 s | details |
#10 | TIME LIMIT EXCEEDED | -- | details |
#11 | TIME LIMIT EXCEEDED | -- | details |
#12 | WRONG ANSWER | 0.07 s | details |
#13 | TIME LIMIT EXCEEDED | -- | 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 secondusing 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*yy.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 lengthfor(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: TIME LIMIT EXCEEDED
input |
---|
21 32 5
3 5 15 8 R 334126231002222122244321129954... |
correct output |
---|
1959913839402 |
user output |
---|
(empty) |
Test 9
Verdict: WRONG ANSWER
input |
---|
29 44 5
20 21 3 26 L 760376683503757740684647181292... |
correct output |
---|
62013683483 |
user output |
---|
-1 |
Test 10
Verdict: TIME LIMIT EXCEEDED
input |
---|
40 40 5
28 23 15 9 L 137103427205590752679014023441... |
correct output |
---|
57788077454 |
user output |
---|
(empty) |
Test 11
Verdict: TIME LIMIT EXCEEDED
input |
---|
45 49 5
12 15 34 30 R 860736165053314133032790918044... |
correct output |
---|
10477495826046 |
user output |
---|
(empty) |
Test 12
Verdict: WRONG ANSWER
input |
---|
47 49 5
17 26 8 40 R 384608891563515730952391281457... |
correct output |
---|
781942227216 |
user output |
---|
-1 |
Test 13
Verdict: TIME LIMIT EXCEEDED
input |
---|
50 50 5
4 35 27 43 L 998166911112259286230836653527... |
correct output |
---|
9298781157357368 |
user output |
---|
(empty) |