QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557313#8668. 回文路径h_rains0 2ms10824kbC++141.9kb2024-09-11 08:55:112024-09-11 08:55:11

Judging History

你现在查看的是最新测评结果

  • [2024-09-11 08:55:11]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:10824kb
  • [2024-09-11 08:55:11]
  • 提交

answer

bool M1;
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ull unsigned long long
#define LL __int128
#define pc(x) __builtin_popcount(x)
#define Pii pair<int,int>
#define Pll pair<ll,ll>
#define Pull pair<ull,ull>
#define vec vector<int>
#define pb push_back
#define fir first
#define sec second
#define xzl cerr<<"xzl\n"
#define dyh cerr<<"dyh\n"
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define UF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define uni(x,y) uniform_int_distribution<int>(x,y)(rng)
#define unl(x,y) uniform_int_distribution<ll>(x,y)(rng)
#define unr(x,t) uniform_real_distribution<double>(rng)
#define look_memory cerr<<'\n'<<abs(&M1-&M2)/1024.0/1024<<'\n'
#define look_time cerr<<'\n'<<1.0*clock()/CLOCKS_PER_SEC<<'\n'
const int INF=0x3f3f3f3f;
const int Mod=1e9+7;
mt19937 rng(time(0)^(*new int));
template<typename T>
inline void inc(T &a,T b){
	if(b<0) b+=Mod;
	a+=b;
	if(a>=Mod) a-=Mod;
}
template<typename T>
inline void dec(T &a,T b){
	if(b<0) b+=Mod;
	a-=b;
	if(a<0) a+=Mod;
}
template<typename T>
inline void muc(T &a,T b){
	a=a*b%Mod;
}
template<typename T>
inline bool chkmin(T &a,T b){
	if(a<=b) return false;
	a=b;
	return true;
}
template<typename T>
inline bool chkmax(T &a,T b){
	if(a>=b) return false;
	a=b;
	return true;
}
int n,ans;
char sx[11000010],s[22000010];
int lp[22000010];
void mnc(){
	for(int i=1,r=0,mid=0;i<=2*n;i++){
		if(i<=r) lp[i]=min(r-i+1,lp[2*mid-i]);
		while(s[i-lp[i]]==s[i+lp[i]]) lp[i]++;
		if(chkmax(r,i+lp[i]-1)) mid=i;
	}
}
bool M2;
int main(){
	srand(time(0)^(*new int));
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
        cin>>n;
	cin>>(sx+1);
	s[0]='~',s[1]='#';
	F(i,1,n) s[i*2]=sx[i],s[i*2+1]='#';
	mnc();
	F(i,1,2*n) chkmax(ans,lp[i]-1);
	cout<<ans;
	look_memory;
	look_time;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 30
Accepted
time: 0ms
memory: 8076kb

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Wrong Answer
time: 1ms
memory: 7972kb

input:

1000
wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...

output:

4

result:

wrong answer 1st lines differ - expected: '7', found: '4'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 20
Accepted
time: 2ms
memory: 8856kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

9

result:

ok single line: '9'

Test #12:

score: 0
Wrong Answer
time: 0ms
memory: 10824kb

input:

100000
fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...

output:

7

result:

wrong answer 1st lines differ - expected: '9', found: '7'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%