oj.uz

Submission #955105

# Submission time Handle Problem Language Result Execution time Memory
955105 2024-03-29T11:51:17 Z IUA_Hasin Mutating DNA (IOI21_dna) C++17
22 / 100
 1500 ms 8276 KB 
#include <bits/stdc++.h>
 
#define endl                                "\n"
#define finp                                for(int i=0; i<n; i++)
#define fknp                                for(int k=0; k<n; k++)
#define yeap                                cout<<"YES"<<endl
#define nope                                cout<<"NO"<<endl
#define inpintn                             int n; cin>>n
#define inpintarrn                          int arr[n]; for(int i=0; i<n; i++){cin>>arr[i];}
#define inpllarrn                           long long arr[n]; for(int i=0; i<n; i++){cin>>arr[i];}
#define ll                                  long long
 
using namespace std;

#include "dna.h"

ll const N = 1e5+10;
string aa, bb;
ll arra[N], arrc[N], arrt[N];
ll brra[N], brrc[N], brrt[N];

void init(std::string a, std::string b) {
	aa = a;
	bb = b;
	ll siz = a.size();
	for(int i=0; i<siz; i++){
		if(a[i]=='A'){
			arra[i+1] = arra[i]+1;
			arrc[i+1] = arrc[i];
			arrt[i+1] = arrt[i];
		} else if(a[i]=='C'){
			arra[i+1] = arra[i];
			arrc[i+1] = arrc[i]+1;
			arrt[i+1] = arrt[i];
		} else {
			arra[i+1] = arra[i];
			arrc[i+1] = arrc[i];
			arrt[i+1] = arrt[i]+1;
		}

		if(b[i]=='A'){
			brra[i+1] = brra[i]+1;
			brrc[i+1] = brrc[i];
			brrt[i+1] = brrt[i];
		} else if(b[i]=='C'){
			brra[i+1] = brra[i];
			brrc[i+1] = brrc[i]+1;
			brrt[i+1] = brrt[i];
		} else {
			brra[i+1] = brra[i];
			brrc[i+1] = brrc[i];
			brrt[i+1] = brrt[i]+1;
		}
	}
}

int get_distance(int x, int y) {
	x = x+1;
	y = y+1;
	ll siz1 = aa.size();
	ll diff[siz1+1];
	diff[0] = 0;
	for(int i=0; i<siz1; i++){
		char p = aa[i];
		char q = bb[i];
		if(p!=q){
			diff[i+1] = diff[i]+1;
		} else {
			diff[i+1] = diff[i];
		}
	}

	ll xa = arra[y]-arra[x-1];
	ll xc = arrc[y]-arrc[x-1];
	ll xt = arrt[y]-arrt[x-1];	
	ll ya = brra[y]-brra[x-1];
	ll yc = brrc[y]-brrc[x-1];
	ll yt = brrt[y]-brrt[x-1];
	ll d = diff[y]-diff[x-1];

	if(xa==ya && xc==yc && xt==yt){
		ll ans = d/2;
		return ans;
	} else {
		return -1;
	}

}

Subtask #1
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1535 ms 8020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 232 ms 6716 KB Output is correct
5 Correct 252 ms 6992 KB Output is correct
6 Correct 232 ms 6724 KB Output is correct
7 Correct 219 ms 6236 KB Output is correct
8 Correct 237 ms 6796 KB Output is correct
9 Correct 116 ms 6748 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 232 ms 6716 KB Output is correct
5 Correct 252 ms 6992 KB Output is correct
6 Correct 232 ms 6724 KB Output is correct
7 Correct 219 ms 6236 KB Output is correct
8 Correct 237 ms 6796 KB Output is correct
9 Correct 116 ms 6748 KB Output is correct
10 Execution timed out 1542 ms 8276 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 232 ms 6716 KB Output is correct
5 Correct 252 ms 6992 KB Output is correct
6 Correct 232 ms 6724 KB Output is correct
7 Correct 219 ms 6236 KB Output is correct
8 Correct 237 ms 6796 KB Output is correct
9 Correct 116 ms 6748 KB Output is correct
10 Incorrect 168 ms 6236 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1535 ms 8020 KB Time limit exceeded
2 Halted 0 ms 0 KB -