Submission #398513

#	Time	Username	Problem	Language	Result	Execution time	Memory
398513		model_code	Brperm (RMI20_brperm)	C++17	100 / 100	1576 ms	10276 KiB

brperm

/**
* user:  bojkovic-39f
* fname: Filip
* lname: Bojkovic
* task:  Brperm
* score: 100.0
* date:  2020-12-03 12:12:21.337839
*/
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#include "brperm.h"
#define xx first
#define yy second

using namespace std;

string t="";
const int maxn=500001;
const int maxk=21;
pair<int,int> obrnuti[maxn];
int broja[maxn];
int brojb[maxn];

int obrnuto(int a,int k){
	return obrnuti[a].first*(1<<(k-obrnuti[a].second));
}

void init3(){
	broja[0]=(t[0]=='a');
	brojb[0]=(t[0]=='b');
	for(int i=1;i<t.size();i++){
		broja[i]=broja[i-1];
		brojb[i]=brojb[i-1];
		if(t[i]=='a') broja[i]++;
		else if(t[i]=='b') brojb[i]++;
	}
}

void init2(int n){
	for(int i=0;i<n;i++){
		int res=0;
		int tren=i;
		int koliko=0;
		while(tren>0){
			koliko++;
			res=(res<<1);
			res+=tren&1;
			tren/=2;
		}
		obrnuti[i]={res,koliko};
	}
}

void init(int n, const char s[]) {
	init2(n);
	for(int i=0;i<n;i++) t+=s[i];
	init3();
	return;
}

int stabre(int l,int r,int* niz){
	int ret=niz[r];
	if(l>0) ret-=niz[l-1];
	return ret;
}

int query(int i, int k) {
	if(i+(1<<k)>t.size()) return 0;
	/*for(pair<int,int> j:novi[k]){
		if(t[j.xx-i]!=t[j.yy-i]) return 0;
	}*/
	if(stabre(i,(i+(1<<k))-1,broja)==(1<<k)) return 1;
	if(stabre(i,(i+(1<<k))-1,brojb)==(1<<k)) return 1;
	for(int j=i;j<(i+(1<<k));j++){
		//cout<<j<<" "<<i+obrnuto(j-i,k)<<"\n";
		if(t[j]!=t[i+obrnuto(j-i,k)])
			return 0;
	}
	return 1;
}

Compilation message (stderr)

brperm.cpp: In function 'void init3()':
brperm.cpp:31:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i=1;i<t.size();i++){
      |              ~^~~~~~~~~
brperm.cpp: In function 'int query(int, int)':
brperm.cpp:68:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  if(i+(1<<k)>t.size()) return 0;
      |     ~~~~~~~~^~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 37 / 37
• Subtask 3: 17 / 17
• Subtask 4: 33 / 33