Submission #403723

#	Time	Username	Problem	Language	Result	Execution time	Memory
403723		Nicholas_Patrick	Brperm (RMI20_brperm)	C++17	100 / 100	2097 ms	27316 KiB

brperm

#include "brperm.h"
// #include "grader.cpp"
#include <cstdio>
#include <queue>
#include <string>
#include <array>
using namespace std;

// const unsigned hmod[]={
// 	0x3fffffdd,
// 	0x3fffffd7,
// 	0x3fffffad
// };
const unsigned hmod=0x7fffffff;

inline unsigned reduce(long long x){
	return (x&hmod)+(x>>31);
}
const unsigned base=1001;

const unsigned maxn=500000;
const unsigned maxflog2n=31-__builtin_clz(maxn);
const unsigned maxflog4n=maxflog2n+1>>1;
const unsigned maxsqrtn=1<<maxflog4n;

unsigned powers[maxn+1];
unsigned reverse[maxflog4n+1][maxsqrtn];
unsigned prefixhash[maxn+1];

string s;

unsigned prechash[maxflog2n+1][maxn];
void init(int n, const char S[]) {
	s.resize(n);
	for(unsigned i=0; i<n; i++)
		s[i]=S[i];

	powers[0]=1;
	for(unsigned j=0; j<maxn; j++)
		powers[j+1]=reduce((long long)powers[j]*base);

	reverse[0][0]=0;
	for(unsigned i=0; i<maxflog4n; i++){
		for(unsigned j=0; j<1<<i; j++){
			reverse[i+1][j]=reverse[i][j]*2;
			reverse[i+1][j+(1<<i)]=reverse[i][j]*2+1;
		}
	}

	prefixhash[0]=0;
	for(unsigned j=0; j<n; j++)
		prefixhash[j+1]=reduce(prefixhash[j]+(long long)s[j]*powers[j]);

	for(unsigned i=maxflog2n; i!=maxflog4n; i--){
		unsigned querlog=i>>1;
		unsigned preclog=i-querlog;
		unsigned prec=1<<preclog;
		for(unsigned j=0; (prec-1<<querlog)+j<n; j++){
			prechash[i][j]=0;
			for(unsigned l=0; l<prec; l++)
				prechash[i][j]=reduce(prechash[i][j]+(long long)powers[l]*s[(reverse[preclog][l]<<querlog)+j]);
		}
	}
	return;
}

int query(int i, int k){
	if(i+(1<<k)>s.size())
		return 0;
	if(k<=maxflog4n){
		for(unsigned j=1<<k; j--;){
			if(s[j+i]!=s[reverse[k][j]+i])
				return 0;
		}
		return 1;
	}
	unsigned querlog=k>>1;
	unsigned preclog=k-querlog;
	unsigned prec=1<<preclog;
	for(unsigned j=1<<querlog; j--;){
		if(((long long)prechash[k][j+i]*powers[(reverse[querlog][j]<<preclog)+i]-prefixhash[(reverse[querlog][j]+1<<preclog)+i]+prefixhash[(reverse[querlog][j]<<preclog)+i])%hmod)
			return 0;
	}
	return 1;
}

Compilation message (stderr)

brperm.cpp:23:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | const unsigned maxflog4n=maxflog2n+1>>1;
      |                          ~~~~~~~~~^~
brperm.cpp: In function 'void init(int, const char*)':
brperm.cpp:35:21: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   35 |  for(unsigned i=0; i<n; i++)
      |                    ~^~
brperm.cpp:44:22: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   44 |   for(unsigned j=0; j<1<<i; j++){
      |                     ~^~~~~
brperm.cpp:51:21: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   51 |  for(unsigned j=0; j<n; j++)
      |                    ~^~
brperm.cpp:58:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   58 |   for(unsigned j=0; (prec-1<<querlog)+j<n; j++){
      |                      ~~~~^~
brperm.cpp:58:40: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   58 |   for(unsigned j=0; (prec-1<<querlog)+j<n; j++){
      |                     ~~~~~~~~~~~~~~~~~~~^~
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)>s.size())
      |     ~~~~~~~~^~~~~~~~~
brperm.cpp:70:6: warning: comparison of integer expressions of different signedness: 'int' and 'const unsigned int' [-Wsign-compare]
   70 |  if(k<=maxflog4n){
      |     ~^~~~~~~~~~~
brperm.cpp:81:107: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   81 |   if(((long long)prechash[k][j+i]*powers[(reverse[querlog][j]<<preclog)+i]-prefixhash[(reverse[querlog][j]+1<<preclog)+i]+prefixhash[(reverse[querlog][j]<<preclog)+i])%hmod)
      |                                                                                        ~~~~~~~~~~~~~~~~~~~^~
brperm.cpp:79:11: warning: unused variable 'prec' [-Wunused-variable]
   79 |  unsigned prec=1<<preclog;
      |           ^~~~

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