oj.uz

Submission #398513

# Submission time Handle Problem Language Result Execution time Memory
398513 2021-05-04T12:47:06 Z model_code Brperm (RMI20_brperm) C++17
100 / 100
 1576 ms 10276 KB 
/**
* 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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 30 ms 2408 KB Output is correct
4 Correct 29 ms 2372 KB Output is correct
5 Correct 30 ms 2372 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1576 ms 10276 KB Output is correct
2 Correct 182 ms 10232 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 30 ms 2408 KB Output is correct
4 Correct 29 ms 2372 KB Output is correct
5 Correct 30 ms 2372 KB Output is correct
6 Correct 1576 ms 10276 KB Output is correct
7 Correct 182 ms 10232 KB Output is correct
8 Correct 157 ms 10148 KB Output is correct
9 Correct 162 ms 10208 KB Output is correct
10 Correct 156 ms 10240 KB Output is correct