QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#84916#5338. PalindromesExplodingKonjac6.25 427ms4024kbC++174.9kb2023-03-06 21:00:142023-03-06 21:00:57

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-06 21:00:57]
  • 评测
  • 测评结果:6.25
  • 用时:427ms
  • 内存:4024kb
  • [2023-03-06 21:00:14]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
//#define OPENIOBUF

namespace FastIO
{

class FastIOBase
{
 protected:
#ifdef OPENIOBUF
	static const int BUFSIZE=1<<22;
	char buf[BUFSIZE+1];
	int buf_p=0;
#endif
	FILE *target;
 public:
#ifdef OPENIOBUF
	virtual void flush()=0;
#endif
	FastIOBase(FILE *f): target(f){}
	~FastIOBase()=default;
};

class FastOutput: public FastIOBase
{
#ifdef OPENIOBUF
 public:
	inline void flush()
		{ fwrite(buf,1,buf_p,target),buf_p=0; }
#endif
 protected:
	inline void __putc(char x)
	{
#ifdef OPENIOBUF
		if(buf[buf_p++]=x,buf_p==BUFSIZE)flush();
#else
		putc(x,target);
#endif
	}
	template<typename T>
	inline void __write(T x)
	{
		static char stk[64],*top;top=stk;
		if(x<0) return __putc('-'),__write(-x);
		do *(top++)=x%10,x/=10; while(x);
		for(;top!=stk;__putc(*(--top)+'0'));
	}
 public:
	FastOutput(FILE *f=stdout): FastIOBase(f){}
#ifdef OPENIOBUF
	inline void setTarget(FILE *f) { this->flush(),target=f; }
	~FastOutput(){ flush(); }
#else
	inline void setTarget(FILE *f) { target=f; }
#endif
	template<typename ...T>
	inline void writesp(const T &...x)
		{ initializer_list<int>{(this->operator<<(x),__putc(' '),0)...}; }
	template<typename ...T>
	inline void writeln(const T &...x)
		{ initializer_list<int>{(this->operator<<(x),__putc('\n'),0)...}; }
	inline FastOutput &operator <<(char x)
		{ return __putc(x),*this; }
	inline FastOutput &operator <<(const char *s)
		{ for(;*s;__putc(*(s++)));return *this; }
	inline FastOutput &operator <<(const string &s)
		{ return (*this)<<s.c_str(); }
	template<typename T,typename=typename enable_if<is_integral<T>::value>::type>
	inline FastOutput &operator <<(const T &x)
		{ return __write(x),*this; }
}qout;

class FastInput: public FastIOBase
{
#ifdef OPENIOBUF
 public:
	inline void flush()
		{ buf[fread(buf,1,BUFSIZE,target)]='\0',buf_p=0; }
#endif
 protected:
	inline char __getc()
	{
#ifdef OPENIOBUF
		if(buf_p==BUFSIZE) flush();
		return buf[buf_p++];
#else
		return getc(target);
#endif
	}
 public:
#ifdef OPENIOBUF
	FastInput(FILE *f=stdin): FastIOBase(f){ buf_p=BUFSIZE; }
	inline void setTarget(FILE *f) { this->flush(),target=f; }
#else
	FastInput(FILE *f=stdin): FastIOBase(f){}
	inline void setTarget(FILE *f) { target=f; }
#endif
	inline char getchar() { return __getc(); }
	template<typename ...T>
	inline void read(T &...x)
		{ initializer_list<int>{(this->operator>>(x),0)...}; }
	inline FastInput &operator >>(char &x)
		{ while(isspace(x=__getc()));return *this; }
	template<typename T,typename=typename enable_if<is_integral<T>::value>::type>
	inline FastInput &operator >>(T &x)
	{
		static char ch,sym;x=sym=0;
		while(isspace(ch=__getc()));
		if(ch=='-') sym=1,ch=__getc();
		for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=__getc());
		return sym?x=-x:x,*this;
	}
	inline FastInput &operator >>(char *s)
	{
		while(isspace(*s=__getc()));
		for(;!isspace(*s) && *s && ~*s;*(++s)=__getc());
		return *s='\0',*this;
	}
	inline FastInput &operator >>(string &s)
	{
		char str_buf[(1<<8)+1],*p=str_buf;
		char *const buf_end=str_buf+(1<<8);
		while(isspace(*p=__getc()));
		for(s.clear(),p++;;p=str_buf)
		{
			for(;p!=buf_end && !isspace(*p=__getc()) && *p && ~*p;p++);
			*p='\0',s.append(str_buf);
			if(p!=buf_end) break;
		}
		return *this;
	}
}qin;

} // namespace FastIO
using namespace FastIO;

using LL=long long;
using LD=long double;
using UI=unsigned int;
using ULL=unsigned long long;

#ifndef DADALZY
#define FILEIO(file) freopen(file".in","r",stdin),freopen(file".out","w",stdout)
#else
#define FILEIO(file)
#endif

int n,m,p[7505],s1[7505],s2[7505];
char str[7505];
LL ans,tmp[15005],val[15005],t1[15005],t2[15005];
inline void add(int p) { for(int x=p;p<=n+n;t1[p]+=x,t2[p]++,p+=p&-p); }
inline pair<LL,LL> get(int p) { LL x=0,y=0;for(;p;x+=t1[p],y+=t2[p],p-=p&-p);return {x,y}; }
int main()
{
	qin>>(str+1),n=strlen(str+1);
	for(int i=1;i<=n;i++)
	{
		if(str[i]=='G') p[++m]=i;
		s1[i]=s1[i-1]^(str[i]=='G');
		s2[i]=s2[i-1]^(str[i]=='H');
	}
	p[0]=0,p[m+1]=n+1;
	for(int k=1;k<=m;k++)
	{
		auto work=[](int i,int j)
		{
			int mid=(i==j?p[i]:-1);
			fill(t1+1,t1+n+n+1,0);
			fill(t2+1,t2+n+n+1,0);
			for(LL sum=0,cnt=0;i>=1 && j<=m;i--,j++)
			{
				int ll=p[i-1]+1,lr=p[i],rl=p[j],rr=p[j+1]-1;
				int sl=ll+rl,sr=lr+rr;
				if(i!=j) tmp[p[i]+p[j]-1]+=2,sum+=p[i]+p[j],cnt++,add(p[i]+p[j]);
				LL f=0,df=0;
				auto [x,y]=get(sl);
				f+=sl*y-x,df+=y;
				x=sum-x,y=cnt-y;
				f-=sl*y-x,df-=y;
				for(int s=sl;s<=sr;s++)
				{
					val[s]=f,f+=df,df+=tmp[s];
					if(mid==-1) continue;
					val[s]+=abs(2*mid-s)/2;
				}
				for(int l=ll;l<=lr;l++) for(int r=rl;r<=rr;r++)
				{
					int c1=s1[r]^s1[l-1],c2=s2[r]^s2[l-1];
					if(c1 && c2) ans--;
					else ans+=val[l+r];
				}
			}
		};
		work(k,k+1),work(k,k);
	}
	qout<<ans;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 6.25
Accepted
time: 2ms
memory: 3240kb

input:

GHHGGHHGH

output:

12

result:

ok single line: '12'

Test #2:

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

input:

HHHHHHHHGHGGHGGGGHGGGHGGHGGHGGGGHHHHHGGGGHGHHHGGHGGHHGGHGHGHGHGHGHHHGGHHGHGGHGGGHGGGGHHGGHHHGHHGHHGG

output:

199935

result:

wrong answer 1st lines differ - expected: '98047', found: '199935'

Test #3:

score: 0
Wrong Answer
time: 2ms
memory: 3332kb

input:

GGHHHGHGHHHHGHHHHGHGHGGHHHGHGGHHHGGHGHHGGHHHHGGGHHGGGGHHHGGHGHGHHHGGGGHHHHGGGGGHGHGGGHGGGGHHHGHHHHGGGHGGGHHGGHGHHHHHHGHHHHGGHGHHGHHGHGHHHHHHHGGGHGGHGHGHHGHGHGHHHHGGHGHHGGHHHHGHGHGGHGHHGGHHGHGHHHGGHGHG

output:

2015831

result:

wrong answer 1st lines differ - expected: '1377709', found: '2015831'

Test #4:

score: 0
Wrong Answer
time: 3ms
memory: 3352kb

input:

HGGHGHGGGHHHHGGHHGGHHGGHHGHHGHHGHHHGGGGHHGGGGHGGGHGHGHHHGHGGGHGGHHGGGHGHHHHHGHGGHHGHGHGHGHGHHHGGGHGHGGGGHHHHGGHHGHGGGGHHGHGHHGGHGGGHHHHHGGHGHGHGGHGGHHHGHGGHGHHHHGGHHHHGGHHHHHHGGGHHHGGGGHHGGHGGGGHHGHHHHGHGGGGHGHHHHHHGGGGGGGHHGHHHHGGHGHGGHHHHHHHHHGHGGGGHHGGGGGGGHHGHGHHGHHGHGHHHGHHGGGHHGGGGGHGGHGHHHGGH...

output:

27956967

result:

wrong answer 1st lines differ - expected: '18589853', found: '27956967'

Test #5:

score: 0
Wrong Answer
time: 9ms
memory: 3508kb

input:

GHGHGHGHHGGHGGHGHGHGHHGGHHHHHGGGHHGHHHGGHHHHHHHHGHHHHHHGHGHGGHGHGHHHGHGGHGHHHHHGHHHHHGGGHGHHGHGGGGGHHGHGGGHGGGGGHHGHGGHHGGHGHHHGHHHGGHHGHHHHHGGGGHHHHGGGGHGGHHGHHGHHGGGHGHHGHGGGGGHHGHHHHHGHHHHHHGHGGHHHGGGHGHGHGHGHHHGGGGGHHHGHGGHHGGHGGHGHGHHGHGGGHGGGGGGHHHHGGGHGHGGHHGGGHHGGHGHHHHGGGGHGGGHGHGGHHGGGGHGG...

output:

316322497

result:

wrong answer 1st lines differ - expected: '239620295', found: '316322497'

Test #6:

score: 0
Wrong Answer
time: 24ms
memory: 3476kb

input:

GHGHHGHHHHHHHGHHGGHHGGHHHGGHHHGGGHHGHGGGHHGGGHGHGHGGHHHHGGGGHGGHHGGHGHHHGGGHHHGHGHHGHHGGHGGGGGHHHHGGGGHGHHHHHGGHGGGGGHGGHHHHGHGHGGHGGGGGGGGHHHGGHHHHGGHHHHGHGGGGHGGHHHHHHHHGGGHHGHGHHHGGGHGHGGGHHHGGHHHGHHHHHHGHGHGHHGHHGHGHHHGHHGGGGHGHGHHGHGHHHGGHGGGGGHGGGHHHHGHGHHHHGHHGGHHHHGHGGHHGGGHGHGHHGHHGHGHHGGGG...

output:

4556264671

result:

wrong answer 1st lines differ - expected: '3749745269', found: '4556264671'

Test #7:

score: 0
Wrong Answer
time: 214ms
memory: 3724kb

input:

HHHHGGHHHHHHHHGGGHHGHHGHGGHHHGHHGHHHGGGHHHHGHGGGGHGHGGGGHHHHHGHHHGHGHGGGGGGGGHHGHHGGHGHGGGGGHGGHHHHGHHGGHGGHHGGHHGGHGHGGGGHHHGGHGGGHHGGHGGGGGHHHHGHHHGHGGGGGGHGHHHGGHHGHGHHHHHHGHGGHGGHGHGHGGGHGHGHHGHGHGGHGHHHGHGHGHGGHGGHHGHHHGHGGGGGHGGHHHGHHGGGHHGGGHGGHHHHGHHHGGGHGHGGGHGGHGGGHHGGHHGHHHHGHHGHHHGGHHGHH...

output:

93184968044

result:

wrong answer 1st lines differ - expected: '81813329996', found: '93184968044'

Test #8:

score: 0
Wrong Answer
time: 165ms
memory: 3796kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHGHHHHHHHHHHHGHHHHHHHGGHHHHHHHHHHHHH...

output:

2225085984431

result:

wrong answer 1st lines differ - expected: '1993575766369', found: '2225085984431'

Test #9:

score: 0
Wrong Answer
time: 179ms
memory: 3720kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHGHHHGHHHHGHHHHHHHHHHHHHHHGHGHHHHHHHHGHHHHHHGHHHHHHHHHHHH...

output:

2287972543724

result:

wrong answer 1st lines differ - expected: '1936319118814', found: '2287972543724'

Test #10:

score: 0
Wrong Answer
time: 167ms
memory: 3684kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHGHHHGHHHHHHHHHHHHHHHHHHHHHHH...

output:

2696979983858

result:

wrong answer 1st lines differ - expected: '1906624646754', found: '2696979983858'

Test #11:

score: 0
Wrong Answer
time: 169ms
memory: 3716kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHGHGHHHHHHHHHHGHHHHGHHHHHGHGHHHHHHHHHHHHHHHH...

output:

2313837099839

result:

wrong answer 1st lines differ - expected: '2056784748165', found: '2313837099839'

Test #12:

score: 0
Wrong Answer
time: 427ms
memory: 3896kb

input:

HHGHGHHGHGHGGHGHGGHGGHHGGGGGGGGGHGHGGGGHHGHGGHGGHGHGGGGGGHGGHHHGHHHGGHGHHHGGHHGGGHHHGGHHGGHHHGHGHHHHHGHGHHHHHGHGGGGHGHHHHHGHHGHGHHHHHGGGGGHGHHGGHGGGHHGHGGHGHHHHGHHGHHHGGHHGGGGGGHGGHHHGHGGHHGGGGHGGGGHHGGHHGGHGGHGGGHHHGGHGHGHGHHGGHGHGGGHHHHGGGHHGHHGHHHHGHGGGHHGHGGGGHHGHHGHHHGHGHHHGHHGGGHGHGHHHHHGHGGGH...

output:

554558237944

result:

wrong answer 1st lines differ - expected: '516066376178', found: '554558237944'

Test #13:

score: 0
Wrong Answer
time: 376ms
memory: 3884kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH...

output:

10640883121917

result:

wrong answer 1st lines differ - expected: '9878475549129', found: '10640883121917'

Test #14:

score: 0
Wrong Answer
time: 411ms
memory: 3760kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH...

output:

11672625868341

result:

wrong answer 1st lines differ - expected: '9918848392027', found: '11672625868341'

Test #15:

score: 0
Wrong Answer
time: 415ms
memory: 4024kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGGHHHHHHHHHHHHHHHGHHHHHHH...

output:

10643147945493

result:

wrong answer 1st lines differ - expected: '9882416063183', found: '10643147945493'

Test #16:

score: 0
Wrong Answer
time: 409ms
memory: 3852kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHGHHHH...

output:

10466399736040

result:

wrong answer 1st lines differ - expected: '9847097832382', found: '10466399736040'