oj.uz

Submission #403723

# Submission time Handle Problem Language Result Execution time Memory
403723 2021-05-13T11:44:42 Z Nicholas_Patrick Brperm (RMI20_brperm) C++17
100 / 100
 2097 ms 27316 KB 
#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

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

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

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2252 KB Output is correct
2 Correct 3 ms 2252 KB Output is correct
3 Correct 163 ms 6136 KB Output is correct
4 Correct 164 ms 6248 KB Output is correct
5 Correct 163 ms 6180 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2097 ms 27316 KB Output is correct
2 Correct 1863 ms 26836 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2252 KB Output is correct
2 Correct 3 ms 2252 KB Output is correct
3 Correct 163 ms 6136 KB Output is correct
4 Correct 164 ms 6248 KB Output is correct
5 Correct 163 ms 6180 KB Output is correct
6 Correct 2097 ms 27316 KB Output is correct
7 Correct 1863 ms 26836 KB Output is correct
8 Correct 1873 ms 26920 KB Output is correct
9 Correct 1839 ms 26848 KB Output is correct
10 Correct 1844 ms 26692 KB Output is correct