oj.uz

Submission #208463

# Submission time Handle Problem Language Result Execution time Memory
208463 2020-03-11T09:23:10 Z Fasho Genetics (BOI18_genetics) C++14
100 / 100
 713 ms 185480 KB 
#include <bits/stdc++.h>
#define N 5005
#define ll long long int 	
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("badhair.gir","r",stdin);freopen ("badhair.cik","w",stdout);
#define mod 1000000007
#define fs(x,y) for(ll i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define INF 1000000000005
#define ull unsigned long long int
using namespace std;

ll n,m,ar[N][N],sum,t,pw[N],p=5,tut[N][10],top,k;
// ll p=100003;
char s[N][N];

ll add(ll x,ll y)
{
	x%=mod;
	y%=mod;
	x+=y;
	x%=mod;
	while(x<0)
		x+=mod;
	return x;
}
ll cik(ll x,ll y)
{
	x%=mod;
	y%=mod;
	x-=y;
	x%=mod;
	while(x<0)
		x+=mod;
	return x;
}
ll carp(ll x,ll y)
{
	x%=mod;
	y%=mod;
	x*=y;
	x%=mod;
	while(x<0)
		x+=mod;
	return x;
}



int main()
{
	fast;
	cin>>n>>m>>k;
	// cout<<k<<endl;
	pw[0]=1;
	for(int i=1;i<=5e3;i++)
		pw[i]=carp(pw[i-1],p);
	// cout<<k<<endl;
	fo(i,1,n)
		cin>>s[i]+1;
	fo(i,1,n)
		fo(j,1,m)
		{
			if(s[i][j]=='A')
				ar[i][j]=1;
			if(s[i][j]=='T')
				ar[i][j]=2;
			if(s[i][j]=='G')
				ar[i][j]=3;
			if(s[i][j]=='C')
				ar[i][j]=4;
		}
	for(int i=1;i<=n;i++)
	{
		// cout<<top<<sp<<pw[i-1]<<sp<<k<<endl;
		top=add(top,carp(pw[i-1],k));
	}

	fo(i,1,n)
	{
		fo(j,1,m)
		{
			for(int h=1;h<=4;h++)
			{
				if(h==ar[i][j])
					continue;
				tut[j][h]=add(tut[j][h],pw[i-1]);
				// cout<<pw[i]<<endl;
			}
		}
	}
	// for(int i=1;i<=4;i++)
	// {
	// 		for(int j=1;j<=m;j++)
	// 			cout<<tut[j][i]<<sp;
	// 	cout<<endl;
	// }
	// cout<<endl;
	for(int i=1;i<=n;i++)
	{
		ll x=0;
		for(int j=1;j<=m;j++)
			x=add(x,tut[j][ar[i][j]]);
		// cout<<i<<sp<<x<<sp<<cik(top,carp(pw[i-1],k))<<sp<<top<<endl;
		if(x==cik(top,carp(pw[i-1],k)))
			return cout<<i,0;
	}
	cout<<top<<endl;

}

Compilation message

genetics.cpp: In function 'int main()':
genetics.cpp:69:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   cin>>s[i]+1;
        ~~~~^~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1144 KB Output is correct
2 Correct 6 ms 1272 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 1016 KB Output is correct
5 Correct 5 ms 1144 KB Output is correct
6 Correct 5 ms 1276 KB Output is correct
7 Correct 5 ms 888 KB Output is correct
8 Correct 6 ms 504 KB Output is correct
9 Correct 5 ms 1016 KB Output is correct
10 Correct 6 ms 1272 KB Output is correct
11 Correct 5 ms 1144 KB Output is correct
12 Correct 6 ms 1272 KB Output is correct
13 Correct 5 ms 1276 KB Output is correct
14 Correct 6 ms 1272 KB Output is correct
15 Correct 6 ms 1272 KB Output is correct
16 Correct 5 ms 1144 KB Output is correct
17 Correct 5 ms 504 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 37112 KB Output is correct
2 Correct 128 ms 45136 KB Output is correct
3 Correct 129 ms 43128 KB Output is correct
4 Correct 34 ms 16248 KB Output is correct
5 Correct 121 ms 45176 KB Output is correct
6 Correct 128 ms 45176 KB Output is correct
7 Correct 60 ms 19636 KB Output is correct
8 Correct 59 ms 19576 KB Output is correct
9 Correct 112 ms 42360 KB Output is correct
10 Correct 121 ms 42232 KB Output is correct
11 Correct 123 ms 37116 KB Output is correct
12 Correct 98 ms 37372 KB Output is correct
13 Correct 102 ms 37120 KB Output is correct
14 Correct 97 ms 31864 KB Output is correct
15 Correct 87 ms 32248 KB Output is correct
16 Correct 96 ms 33528 KB Output is correct
17 Correct 133 ms 43296 KB Output is correct
18 Correct 118 ms 42872 KB Output is correct
19 Correct 127 ms 43452 KB Output is correct
20 Correct 115 ms 42720 KB Output is correct
21 Correct 124 ms 43284 KB Output is correct
22 Correct 136 ms 42976 KB Output is correct
23 Correct 136 ms 43000 KB Output is correct
24 Correct 134 ms 43036 KB Output is correct
25 Correct 132 ms 42788 KB Output is correct
26 Correct 120 ms 43128 KB Output is correct
27 Correct 119 ms 42744 KB Output is correct
28 Correct 130 ms 42744 KB Output is correct
29 Correct 127 ms 43068 KB Output is correct
30 Correct 111 ms 45240 KB Output is correct
31 Correct 116 ms 45176 KB Output is correct
32 Correct 122 ms 45304 KB Output is correct
33 Correct 5 ms 504 KB Output is correct
34 Correct 7 ms 1272 KB Output is correct
35 Correct 5 ms 504 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 37112 KB Output is correct
2 Correct 128 ms 45136 KB Output is correct
3 Correct 129 ms 43128 KB Output is correct
4 Correct 34 ms 16248 KB Output is correct
5 Correct 121 ms 45176 KB Output is correct
6 Correct 128 ms 45176 KB Output is correct
7 Correct 60 ms 19636 KB Output is correct
8 Correct 59 ms 19576 KB Output is correct
9 Correct 112 ms 42360 KB Output is correct
10 Correct 121 ms 42232 KB Output is correct
11 Correct 123 ms 37116 KB Output is correct
12 Correct 98 ms 37372 KB Output is correct
13 Correct 102 ms 37120 KB Output is correct
14 Correct 97 ms 31864 KB Output is correct
15 Correct 87 ms 32248 KB Output is correct
16 Correct 96 ms 33528 KB Output is correct
17 Correct 133 ms 43296 KB Output is correct
18 Correct 118 ms 42872 KB Output is correct
19 Correct 127 ms 43452 KB Output is correct
20 Correct 115 ms 42720 KB Output is correct
21 Correct 124 ms 43284 KB Output is correct
22 Correct 136 ms 42976 KB Output is correct
23 Correct 136 ms 43000 KB Output is correct
24 Correct 134 ms 43036 KB Output is correct
25 Correct 132 ms 42788 KB Output is correct
26 Correct 120 ms 43128 KB Output is correct
27 Correct 119 ms 42744 KB Output is correct
28 Correct 130 ms 42744 KB Output is correct
29 Correct 127 ms 43068 KB Output is correct
30 Correct 111 ms 45240 KB Output is correct
31 Correct 116 ms 45176 KB Output is correct
32 Correct 122 ms 45304 KB Output is correct
33 Correct 5 ms 504 KB Output is correct
34 Correct 7 ms 1272 KB Output is correct
35 Correct 5 ms 504 KB Output is correct
36 Correct 521 ms 162040 KB Output is correct
37 Correct 572 ms 185196 KB Output is correct
38 Correct 638 ms 180728 KB Output is correct
39 Correct 232 ms 84056 KB Output is correct
40 Correct 615 ms 185080 KB Output is correct
41 Correct 318 ms 92924 KB Output is correct
42 Correct 312 ms 92920 KB Output is correct
43 Correct 414 ms 136700 KB Output is correct
44 Correct 575 ms 185080 KB Output is correct
45 Correct 617 ms 185080 KB Output is correct
46 Correct 558 ms 185080 KB Output is correct
47 Correct 529 ms 161912 KB Output is correct
48 Correct 547 ms 162040 KB Output is correct
49 Correct 424 ms 138876 KB Output is correct
50 Correct 469 ms 139060 KB Output is correct
51 Correct 511 ms 156328 KB Output is correct
52 Correct 601 ms 180344 KB Output is correct
53 Correct 620 ms 180504 KB Output is correct
54 Correct 511 ms 177396 KB Output is correct
55 Correct 560 ms 177376 KB Output is correct
56 Correct 525 ms 177336 KB Output is correct
57 Correct 625 ms 181112 KB Output is correct
58 Correct 590 ms 181064 KB Output is correct
59 Correct 586 ms 180088 KB Output is correct
60 Correct 562 ms 181108 KB Output is correct
61 Correct 564 ms 180088 KB Output is correct
62 Correct 552 ms 179320 KB Output is correct
63 Correct 550 ms 180984 KB Output is correct
64 Correct 578 ms 180760 KB Output is correct
65 Correct 616 ms 180340 KB Output is correct
66 Correct 623 ms 180324 KB Output is correct
67 Correct 605 ms 181172 KB Output is correct
68 Correct 622 ms 181008 KB Output is correct
69 Correct 554 ms 180148 KB Output is correct
70 Correct 674 ms 180832 KB Output is correct
71 Correct 612 ms 180020 KB Output is correct
72 Correct 617 ms 181368 KB Output is correct
73 Correct 600 ms 180216 KB Output is correct
74 Correct 5 ms 504 KB Output is correct
75 Correct 5 ms 1272 KB Output is correct
76 Correct 5 ms 504 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1144 KB Output is correct
2 Correct 6 ms 1272 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 1016 KB Output is correct
5 Correct 5 ms 1144 KB Output is correct
6 Correct 5 ms 1276 KB Output is correct
7 Correct 5 ms 888 KB Output is correct
8 Correct 6 ms 504 KB Output is correct
9 Correct 5 ms 1016 KB Output is correct
10 Correct 6 ms 1272 KB Output is correct
11 Correct 5 ms 1144 KB Output is correct
12 Correct 6 ms 1272 KB Output is correct
13 Correct 5 ms 1276 KB Output is correct
14 Correct 6 ms 1272 KB Output is correct
15 Correct 6 ms 1272 KB Output is correct
16 Correct 5 ms 1144 KB Output is correct
17 Correct 5 ms 504 KB Output is correct
18 Correct 109 ms 37112 KB Output is correct
19 Correct 128 ms 45136 KB Output is correct
20 Correct 129 ms 43128 KB Output is correct
21 Correct 34 ms 16248 KB Output is correct
22 Correct 121 ms 45176 KB Output is correct
23 Correct 128 ms 45176 KB Output is correct
24 Correct 60 ms 19636 KB Output is correct
25 Correct 59 ms 19576 KB Output is correct
26 Correct 112 ms 42360 KB Output is correct
27 Correct 121 ms 42232 KB Output is correct
28 Correct 123 ms 37116 KB Output is correct
29 Correct 98 ms 37372 KB Output is correct
30 Correct 102 ms 37120 KB Output is correct
31 Correct 97 ms 31864 KB Output is correct
32 Correct 87 ms 32248 KB Output is correct
33 Correct 96 ms 33528 KB Output is correct
34 Correct 133 ms 43296 KB Output is correct
35 Correct 118 ms 42872 KB Output is correct
36 Correct 127 ms 43452 KB Output is correct
37 Correct 115 ms 42720 KB Output is correct
38 Correct 124 ms 43284 KB Output is correct
39 Correct 136 ms 42976 KB Output is correct
40 Correct 136 ms 43000 KB Output is correct
41 Correct 134 ms 43036 KB Output is correct
42 Correct 132 ms 42788 KB Output is correct
43 Correct 120 ms 43128 KB Output is correct
44 Correct 119 ms 42744 KB Output is correct
45 Correct 130 ms 42744 KB Output is correct
46 Correct 127 ms 43068 KB Output is correct
47 Correct 111 ms 45240 KB Output is correct
48 Correct 116 ms 45176 KB Output is correct
49 Correct 122 ms 45304 KB Output is correct
50 Correct 5 ms 504 KB Output is correct
51 Correct 7 ms 1272 KB Output is correct
52 Correct 5 ms 504 KB Output is correct
53 Correct 521 ms 162040 KB Output is correct
54 Correct 572 ms 185196 KB Output is correct
55 Correct 638 ms 180728 KB Output is correct
56 Correct 232 ms 84056 KB Output is correct
57 Correct 615 ms 185080 KB Output is correct
58 Correct 318 ms 92924 KB Output is correct
59 Correct 312 ms 92920 KB Output is correct
60 Correct 414 ms 136700 KB Output is correct
61 Correct 575 ms 185080 KB Output is correct
62 Correct 617 ms 185080 KB Output is correct
63 Correct 558 ms 185080 KB Output is correct
64 Correct 529 ms 161912 KB Output is correct
65 Correct 547 ms 162040 KB Output is correct
66 Correct 424 ms 138876 KB Output is correct
67 Correct 469 ms 139060 KB Output is correct
68 Correct 511 ms 156328 KB Output is correct
69 Correct 601 ms 180344 KB Output is correct
70 Correct 620 ms 180504 KB Output is correct
71 Correct 511 ms 177396 KB Output is correct
72 Correct 560 ms 177376 KB Output is correct
73 Correct 525 ms 177336 KB Output is correct
74 Correct 625 ms 181112 KB Output is correct
75 Correct 590 ms 181064 KB Output is correct
76 Correct 586 ms 180088 KB Output is correct
77 Correct 562 ms 181108 KB Output is correct
78 Correct 564 ms 180088 KB Output is correct
79 Correct 552 ms 179320 KB Output is correct
80 Correct 550 ms 180984 KB Output is correct
81 Correct 578 ms 180760 KB Output is correct
82 Correct 616 ms 180340 KB Output is correct
83 Correct 623 ms 180324 KB Output is correct
84 Correct 605 ms 181172 KB Output is correct
85 Correct 622 ms 181008 KB Output is correct
86 Correct 554 ms 180148 KB Output is correct
87 Correct 674 ms 180832 KB Output is correct
88 Correct 612 ms 180020 KB Output is correct
89 Correct 617 ms 181368 KB Output is correct
90 Correct 600 ms 180216 KB Output is correct
91 Correct 5 ms 504 KB Output is correct
92 Correct 5 ms 1272 KB Output is correct
93 Correct 5 ms 504 KB Output is correct
94 Correct 591 ms 175224 KB Output is correct
95 Correct 582 ms 185336 KB Output is correct
96 Correct 700 ms 182012 KB Output is correct
97 Correct 388 ms 99320 KB Output is correct
98 Correct 250 ms 83960 KB Output is correct
99 Correct 638 ms 185080 KB Output is correct
100 Correct 349 ms 92920 KB Output is correct
101 Correct 327 ms 92920 KB Output is correct
102 Correct 454 ms 136824 KB Output is correct
103 Correct 607 ms 184952 KB Output is correct
104 Correct 694 ms 184952 KB Output is correct
105 Correct 713 ms 184952 KB Output is correct
106 Correct 665 ms 175736 KB Output is correct
107 Correct 501 ms 161912 KB Output is correct
108 Correct 459 ms 139000 KB Output is correct
109 Correct 564 ms 159608 KB Output is correct
110 Correct 574 ms 153336 KB Output is correct
111 Correct 635 ms 184952 KB Output is correct
112 Correct 666 ms 182776 KB Output is correct
113 Correct 584 ms 177400 KB Output is correct
114 Correct 525 ms 177348 KB Output is correct
115 Correct 657 ms 177448 KB Output is correct
116 Correct 675 ms 182648 KB Output is correct
117 Correct 668 ms 182904 KB Output is correct
118 Correct 666 ms 182776 KB Output is correct
119 Correct 659 ms 182136 KB Output is correct
120 Correct 663 ms 182796 KB Output is correct
121 Correct 532 ms 162040 KB Output is correct
122 Correct 560 ms 185480 KB Output is correct
123 Correct 637 ms 180696 KB Output is correct
124 Correct 5 ms 504 KB Output is correct
125 Correct 5 ms 1272 KB Output is correct
126 Correct 5 ms 504 KB Output is correct