Submission #924290

#	Time	Username	Problem	Language	Result	Execution time	Memory
924290		tosivanmak	Mutating DNA (IOI21_dna)	C++17	100 / 100	34 ms	11152 KiB

dna

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll psum[100005][7];
// 1 at 2 ac 3 ta 4 tc 5 ca 6 ct
ll acnt[100005],tcnt[100005],ccnt[100005];
void init(std::string a, std::string b) {
   for(int i=1;i<=6;i++){
       psum[0][i]=0;
   }
   acnt[0]=tcnt[0]=ccnt[0]=0;
   for(int i=0;i<a.length();i++){
       acnt[i+1]=acnt[i],tcnt[i+1]=tcnt[i],ccnt[i+1]=ccnt[i];
       acnt[i+1]+=(a[i]=='A');
       acnt[i+1]-=(b[i]=='A');
       tcnt[i+1]+=(a[i]=='T');
       tcnt[i+1]-=(b[i]=='T');
       ccnt[i+1]+=(a[i]=='C');
       ccnt[i+1]-=(b[i]=='C');
   }
   for(int i=0;i<a.length();i++){
    //    cout<<i<<'\n';
    // cout<<a[i]<<" "<<b[i]<<'\n';
       for(int j=1;j<=6;j++){
           psum[i+1][j]=psum[i][j];
       }
       if(a[i]=='A'&&b[i]=='T'){
           psum[i+1][1]++;
       }
       if(a[i]=='A'&&b[i]=='C'){
           psum[i+1][2]++;
       }
       if(a[i]=='T'&&b[i]=='A'){
           psum[i+1][3]++;
       }
       if(a[i]=='T'&&b[i]=='C'){
           psum[i+1][4]++;
        //    cout<<"fuck\n";
       }
       if(a[i]=='C'&&b[i]=='A'){
           psum[i+1][5]++;
       }
       if(a[i]=='C'&&b[i]=='T'){
           psum[i+1][6]++;
       }
   }
}

int get_distance(int x, int y) {
    x++,y++;
    if(acnt[y]-acnt[x-1]!=0 || tcnt[y]-tcnt[x-1]!=0 || ccnt[y]-ccnt[x-1]!=0){
        return -1;
    }
    ll one=psum[y][1]-psum[x-1][1];
    ll two=psum[y][2]-psum[x-1][2];
    ll three=psum[y][3]-psum[x-1][3];
    ll four=psum[y][4]-psum[x-1][4];
    ll five=psum[y][5]-psum[x-1][5];
    ll six=psum[y][6]-psum[x-1][6];
    // cout<<one<<" "<<two<<" "<<three<<" "<<four<<" "<<five<<" "<<six<<'\n';
    ll lol=min(one,three);
    ll lol2=min(two,five);
    ll lol3=min(four,six);
    // cout<<lol<<" "<<lol2<<" "<<lol3<<'\n';
    one-=lol,three-=lol;
    return lol+lol2+lol3+2*max(one,three);
}

// int main() {
// 	int n, q;
// 	assert(scanf("%d %d", &n, &q) == 2);
// 	char A[n+1], B[n+1];
// 	assert(scanf("%s", A) == 1);
// 	assert(scanf("%s", B) == 1);
// 	std::string a = std::string(A);
// 	std::string b = std::string(B);
// 	std::vector<int> x(q), y(q);
// 	for (int i = 0; i < q; i++) {
// 		assert(scanf("%d %d", &x[i], &y[i]) == 2);
// 	}
// 	fclose(stdin);
// 	std::vector<int> results(q);
// 	init(a, b);
// 	for (int i = 0; i < q; i++) {
// 		results[i] = get_distance(x[i], y[i]);
// 	}
// 	for (int i = 0; i < q; i++) {
// 		printf("%d\n", results[i]);
// 	}
// 	fclose(stdout);
// 	return 0;
// }

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:12:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |    for(int i=0;i<a.length();i++){
      |                ~^~~~~~~~~~~
dna.cpp:21:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |    for(int i=0;i<a.length();i++){
      |                ~^~~~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 22 / 22
• Subtask 3: 13 / 13
• Subtask 4: 28 / 28
• Subtask 5: 16 / 16