Submission #754662

#	Time	Username	Problem	Language	Result	Execution time	Memory
754662		tolbi	Mutating DNA (IOI21_dna)	C++17	100 / 100	68 ms	19020 KiB

dna

#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulHamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
#define author tolbi
#include<bits/stdc++.h>
using namespace std;
template<typename T> vector<int32_t> normalize(vector<T> &rt){vector<int32_t> arr(rt.size());for (int i = 0; i < rt.size(); i++){arr[i]=rt[i];}return arr;}
#define endl '\n'
#define int long long
#define vint(x) vector<int> x
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define tol(bi) (1LL<<((int)(bi)))
#define lsb(x) (x&-x)
const int MOD = 1e9+7;
const int64_t INF = LONG_LONG_MAX;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());

#include "dna.h"
struct BIT{
	vector<int> fenwik;
	BIT(int n){
		fenwik.resize(2*n+2,0);
	}
	void update(int node, int val){
		for (node++;node<fenwik.size();node+=lsb(node)) fenwik[node]+=val;
	}
	int get(int node){
		int rval = 0;
		for (node++;node;node-=lsb(node)) rval+=fenwik[node];
		return rval;
	}
	int query(int l, int r){
		return get(r)-get(l-1);
	}
};
vector<BIT> fenwik;
void init(string a, string b) {
	int n = a.length();
	fenwik.resize(9,BIT(n));
	for (int i = 0; i < n; ++i)
	{
		if (a[i]=='A') a[i]='0';
		if (a[i]=='T') a[i]='1';
		if (a[i]=='C') a[i]='2';
		if (b[i]=='A') b[i]='0';
		if (b[i]=='T') b[i]='1';
		if (b[i]=='C') b[i]='2';
		fenwik[(a[i]-'0')*3+b[i]-'0'].update(i,1);
	}
}

int32_t get_distance(int32_t x, int32_t y) {
	int at = fenwik[1].query(x,y);
	int ac = fenwik[2].query(x,y);
	int tc = fenwik[5].query(x,y);
	int ta = fenwik[3].query(x,y);
	int ca = fenwik[6].query(x,y);
	int ct = fenwik[7].query(x,y);
	int ans=0;
	int temp;
	temp = min(at,ta);
	ans+=temp;
	at-=temp;
	ta-=temp;
	temp = min(tc,ct);
	ans+=temp;
	tc-=temp;
	ct-=temp;
	temp = min(ac,ca);
	ans+=temp;
	ac-=temp;
	ca-=temp;
	if (ac+at+tc+ta+ca+ct==0) return ans;
	if (!((ac&&ct&&ta) || (at&&tc&&ca))) return -1;
	if (ac){
		if (ac!=ct || ac!=ta) return -1;
		ans+=ac*2;
	}
	else {
		if( ca!=tc || ca!=at) return -1;
		ans+=ca*2;
	}
	return ans;
}

Compilation message (stderr)

dna.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
dna.cpp: In member function 'void BIT::update(long long int, long long int)':
dna.cpp:38:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for (node++;node<fenwik.size();node+=lsb(node)) fenwik[node]+=val;
      |               ~~~~^~~~~~~~~~~~~~

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