# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
499050 |
2021-12-27T06:34:24 Z |
Khizri |
Mutating DNA (IOI21_dna) |
C++17 |
|
420 ms |
51080 KB |
#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define all(v) (v).begin(),(v).end()
string a,b;
char xx[10]={'A','A','A','C','C','C','T','T','T'};
char yy[10]={'A','C','T','A','C','T','A','C','T'};
vector<pair<int,pair<string,string>>>vt;
map<pair<char,char>,int>MP[100050];
void funk(vector<int>vtt){
string a,b;
for(int v:vtt){
a+=xx[v];
b+=yy[v];
}
string qa=a,qb=b;
sort(all(qa));
sort(all(qb));
if(qa!=qb){
return;
}
int ans=0;
string ca=a,cb=b;
while(a!=b){
for(int i=0;i<a.size();i++){
for(int j=i+1;j<b.size();j++){
if(a[i]!=b[i]&&a[j]!=b[j]){
if(a[i]==b[j]&&a[j]==b[i]){
swap(a[i],a[j]);
ans++;
}
}
}
}
for(int i=0;i<a.size();i++){
for(int j=i+1;j<b.size();j++){
if(a[i]!=b[i]&&a[j]!=b[j]){
if(b[i]==a[j]){
swap(a[i],a[j]);
ans++;
}
}
}
}
}
vt.pb({ans,{ca,cb}});
}
void init(std::string ax, std::string ay) {
a=ax,b=ay;
for(int i=0;i<9;i++){
funk({i});
}
for(int i=0;i<9;i++){
for(int j=i;j<9;j++){
funk({i,j});
}
}
for(int i=0;i<9;i++){
for(int j=i;j<9;j++){
for(int k=j;k<9;k++){
funk({i,j,k});
}
}
}
sort(all(vt));
for(int i=0;i<a.size();i++){
if(i>0){
MP[i]=MP[i-1];
}
MP[i][{a[i],b[i]}]++;
}
}
int get_distance(int l, int r) {
int a1=0,a2=0,a3=0,b1=0,b2=0,b3=0;
map<pair<char,char>,int>mp;
mp=MP[r];
if(l>0){
for(auto it=mp.begin();it!=mp.end();it++){
mp[it->F]-=MP[l-1][it->F];
}
}
for(auto it=mp.begin();it!=mp.end();it++){
char q=it->F.F;
int cost=it->S;
if(q=='A'){
a1+=cost;
}
else if(q=='C'){
a2+=cost;
}
else{
a3+=cost;
}
q=it->F.S;
if(q=='A'){
b1+=cost;
}
else if(q=='C'){
b2+=cost;
}
else{
b3+=cost;
}
}
if(a1!=b1||a2!=b2||a3!=b3){
return -1;
}
int ans=0;
for(int i=0;i<vt.size();i++){
string x=vt[i].S.F,y=vt[i].S.S;
int k=vt[i].F;
int cost=1e7;
for(int i=0;i<x.size();i++){
cost=min(cost,mp[{x[i],y[i]}]);
}
if(cost>0){
for(int i=0;i<x.size();i++){
mp[{x[i],y[i]}]-=cost;
}
ans+=cost*k;
}
}
for(auto it=mp.begin();it!=mp.end();it++){
ans+=it->S;
}
return ans;
}
Compilation message
dna.cpp: In function 'void funk(std::vector<int>)':
dna.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i=0;i<a.size();i++){
| ~^~~~~~~~~
dna.cpp:30:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int j=i+1;j<b.size();j++){
| ~^~~~~~~~~
dna.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i=0;i<a.size();i++){
| ~^~~~~~~~~
dna.cpp:40:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int j=i+1;j<b.size();j++){
| ~^~~~~~~~~
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i=0;i<a.size();i++){
| ~^~~~~~~~~
dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:114:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int i=0;i<vt.size();i++){
| ~^~~~~~~~~~
dna.cpp:118:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for(int i=0;i<x.size();i++){
| ~^~~~~~~~~
dna.cpp:122:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(int i=0;i<x.size();i++){
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
294 ms |
25616 KB |
Output is correct |
2 |
Correct |
272 ms |
25860 KB |
Output is correct |
3 |
Correct |
349 ms |
45556 KB |
Output is correct |
4 |
Correct |
355 ms |
49468 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
2 ms |
4936 KB |
Output is correct |
7 |
Correct |
2 ms |
4940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4940 KB |
Output is correct |
2 |
Correct |
2 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4988 KB |
Output is correct |
4 |
Correct |
34 ms |
24316 KB |
Output is correct |
5 |
Correct |
33 ms |
24468 KB |
Output is correct |
6 |
Correct |
34 ms |
24324 KB |
Output is correct |
7 |
Correct |
31 ms |
23108 KB |
Output is correct |
8 |
Correct |
35 ms |
24528 KB |
Output is correct |
9 |
Correct |
33 ms |
24456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4940 KB |
Output is correct |
2 |
Correct |
2 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4988 KB |
Output is correct |
4 |
Correct |
34 ms |
24316 KB |
Output is correct |
5 |
Correct |
33 ms |
24468 KB |
Output is correct |
6 |
Correct |
34 ms |
24324 KB |
Output is correct |
7 |
Correct |
31 ms |
23108 KB |
Output is correct |
8 |
Correct |
35 ms |
24528 KB |
Output is correct |
9 |
Correct |
33 ms |
24456 KB |
Output is correct |
10 |
Correct |
285 ms |
25612 KB |
Output is correct |
11 |
Correct |
285 ms |
25928 KB |
Output is correct |
12 |
Correct |
283 ms |
24888 KB |
Output is correct |
13 |
Correct |
298 ms |
26708 KB |
Output is correct |
14 |
Correct |
275 ms |
27588 KB |
Output is correct |
15 |
Correct |
296 ms |
27520 KB |
Output is correct |
16 |
Correct |
275 ms |
26052 KB |
Output is correct |
17 |
Correct |
302 ms |
26624 KB |
Output is correct |
18 |
Correct |
276 ms |
27496 KB |
Output is correct |
19 |
Correct |
235 ms |
17432 KB |
Output is correct |
20 |
Correct |
263 ms |
17692 KB |
Output is correct |
21 |
Correct |
244 ms |
18116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4940 KB |
Output is correct |
2 |
Correct |
2 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4988 KB |
Output is correct |
4 |
Correct |
34 ms |
24316 KB |
Output is correct |
5 |
Correct |
33 ms |
24468 KB |
Output is correct |
6 |
Correct |
34 ms |
24324 KB |
Output is correct |
7 |
Correct |
31 ms |
23108 KB |
Output is correct |
8 |
Correct |
35 ms |
24528 KB |
Output is correct |
9 |
Correct |
33 ms |
24456 KB |
Output is correct |
10 |
Correct |
83 ms |
44256 KB |
Output is correct |
11 |
Correct |
73 ms |
47964 KB |
Output is correct |
12 |
Correct |
86 ms |
45192 KB |
Output is correct |
13 |
Correct |
77 ms |
47616 KB |
Output is correct |
14 |
Correct |
74 ms |
47920 KB |
Output is correct |
15 |
Correct |
75 ms |
47940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
294 ms |
25616 KB |
Output is correct |
2 |
Correct |
272 ms |
25860 KB |
Output is correct |
3 |
Correct |
349 ms |
45556 KB |
Output is correct |
4 |
Correct |
355 ms |
49468 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
2 ms |
4936 KB |
Output is correct |
7 |
Correct |
2 ms |
4940 KB |
Output is correct |
8 |
Correct |
2 ms |
4940 KB |
Output is correct |
9 |
Correct |
2 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4988 KB |
Output is correct |
11 |
Correct |
34 ms |
24316 KB |
Output is correct |
12 |
Correct |
33 ms |
24468 KB |
Output is correct |
13 |
Correct |
34 ms |
24324 KB |
Output is correct |
14 |
Correct |
31 ms |
23108 KB |
Output is correct |
15 |
Correct |
35 ms |
24528 KB |
Output is correct |
16 |
Correct |
33 ms |
24456 KB |
Output is correct |
17 |
Correct |
285 ms |
25612 KB |
Output is correct |
18 |
Correct |
285 ms |
25928 KB |
Output is correct |
19 |
Correct |
283 ms |
24888 KB |
Output is correct |
20 |
Correct |
298 ms |
26708 KB |
Output is correct |
21 |
Correct |
275 ms |
27588 KB |
Output is correct |
22 |
Correct |
296 ms |
27520 KB |
Output is correct |
23 |
Correct |
275 ms |
26052 KB |
Output is correct |
24 |
Correct |
302 ms |
26624 KB |
Output is correct |
25 |
Correct |
276 ms |
27496 KB |
Output is correct |
26 |
Correct |
235 ms |
17432 KB |
Output is correct |
27 |
Correct |
263 ms |
17692 KB |
Output is correct |
28 |
Correct |
244 ms |
18116 KB |
Output is correct |
29 |
Correct |
83 ms |
44256 KB |
Output is correct |
30 |
Correct |
73 ms |
47964 KB |
Output is correct |
31 |
Correct |
86 ms |
45192 KB |
Output is correct |
32 |
Correct |
77 ms |
47616 KB |
Output is correct |
33 |
Correct |
74 ms |
47920 KB |
Output is correct |
34 |
Correct |
75 ms |
47940 KB |
Output is correct |
35 |
Correct |
3 ms |
4996 KB |
Output is correct |
36 |
Correct |
359 ms |
46932 KB |
Output is correct |
37 |
Correct |
384 ms |
50644 KB |
Output is correct |
38 |
Correct |
359 ms |
48444 KB |
Output is correct |
39 |
Correct |
406 ms |
51080 KB |
Output is correct |
40 |
Correct |
386 ms |
51068 KB |
Output is correct |
41 |
Correct |
70 ms |
48112 KB |
Output is correct |
42 |
Correct |
420 ms |
48468 KB |
Output is correct |
43 |
Correct |
353 ms |
50984 KB |
Output is correct |
44 |
Correct |
406 ms |
50952 KB |
Output is correct |
45 |
Correct |
264 ms |
21868 KB |
Output is correct |
46 |
Correct |
290 ms |
22800 KB |
Output is correct |
47 |
Correct |
267 ms |
22788 KB |
Output is correct |