QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#85818#5338. PalindromesCharlieVinnie37.5 27ms63132kbC++142.1kb2023-03-08 16:16:092023-03-08 16:16:11

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-08 16:16:11]
  • 评测
  • 测评结果:37.5
  • 用时:27ms
  • 内存:63132kb
  • [2023-03-08 16:16:09]
  • 提交

answer

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
using namespace std; using ll = long long;
#define printf(...) (0==0)
const int N=7505;
class Solver{
	int p,d,cur,tr[N*3]; vector<int> his;
public:
	void clear(int _p) { printf("================== clear(%d)\n",_p); p=_p; d=cur=0; for(int x:his) tr[x]=0;; his.clear(); }
	void sett(){
		printf("sett(%d)\n",p);
		his.push_back(p); tr[p]++; d--;
	}
	void move(int x){
		printf("move(%d)\n",x);
		if(x==1) d+=tr[p]*2,cur+=d,p++;
		else cur-=d,p--,d-=tr[p]*2;
	}
	int getv() { printf("getv=%d\n",cur); return cur; }
}S;
char ss[N]; int n,a[N],pp[N],pcnt,tmp[N],ans[N][N];
int main(){
	cin>>(ss+1); n=strlen(ss+1); For(i,1,n) { a[i]=(ss[i]=='H'); if(a[i]) pp[++pcnt]=i; }
	For(i,1,n) For(j,i,n) ans[i][j]=-1;
	pp[0]=0; pp[pcnt+1]=n+1;
	// Even 1
	For(i,1,pcnt-1){
		int p=pp[i]+pp[i+1]; S.clear(p);
		For(j,0,i-1){
			int l=i-j,r=i+1+j; if(r>pcnt) break;
			assert(p>=pp[l]+pp[r]); while(p>pp[l]+pp[r]) S.move(-1),p--;
			S.sett(); while(p>pp[l-1]+1+pp[r]) S.move(-1),p--;
			while(p<=pp[l]+pp[r+1]-1) tmp[p]=S.getv(),S.move(1),p++;
			For(x,pp[l-1]+1,pp[l]) For(y,pp[r],pp[r+1]-1) assert(ans[x][y]==-1),ans[x][y]=tmp[x+y],printf("ans[%d][%d]=%d\n",x,y,ans[x][y]);;
		}
	}
	// Odd 1
	For(i,1,pcnt){
		int p=pp[i]*2; S.clear(p);
		For(j,0,i-1){
			int l=i-j,r=i+j; if(r>pcnt) break;
			assert(p>=pp[l]+pp[r]); while(p>pp[l]+pp[r]) S.move(-1),p--;
			if(j) S.sett();; while(p>pp[l-1]+1+pp[r]) S.move(-1),p--;
			while(p<=pp[l]+pp[r+1]-1) tmp[p]=S.getv(),S.move(1),p++;
			For(x,pp[l-1]+1,pp[l]) For(y,pp[r],pp[r+1]-1) if(~(x+y)&1) assert(ans[x][y]==-1),ans[x][y]=tmp[x+y]+abs((x+y)/2-pp[i]),printf("ans[%d][%d]=%d\n",x,y,ans[x][y]);;
		}
	}
	For(i,0,pcnt) For(x,pp[i]+1,pp[i+1]-1) For(y,x,pp[i+1]-1) ans[x][y]=0;
	printf("\n");
	For(i,1,n) For(j,i,n) printf("ans[%d][%d]=%d\n",i,j,ans[i][j]);
	ll Ans=0; For(x,1,n) For(y,x,n) Ans+=ans[x][y];
	cout<<Ans<<'\n';
	return 0;
}

詳細信息

Test #1:

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

input:

GHHGGHHGH

output:

12

result:

ok single line: '12'

Test #2:

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

input:

HHHHHHHHGHGGHGGGGHGGGHGGHGGHGGGGHHHHHGGGGHGHHHGGHGGHHGGHGHGHGHGHGHHHGGHHGHGGHGGGHGGGGHHGGHHHGHHGHHGG

output:

98047

result:

ok single line: '98047'

Test #3:

score: 6.25
Accepted
time: 1ms
memory: 9536kb

input:

GGHHHGHGHHHHGHHHHGHGHGGHHHGHGGHHHGGHGHHGGHHHHGGGHHGGGGHHHGGHGHGHHHGGGGHHHHGGGGGHGHGGGHGGGGHHHGHHHHGGGHGGGHHGGHGHHHHHHGHHHHGGHGHHGHHGHGHHHHHHHGGGHGGHGHGHHGHGHGHHHHGGHGHHGGHHHHGHGHGGHGHHGGHHGHGHHHGGHGHG

output:

1377709

result:

ok single line: '1377709'

Test #4:

score: 6.25
Accepted
time: 1ms
memory: 17768kb

input:

HGGHGHGGGHHHHGGHHGGHHGGHHGHHGHHGHHHGGGGHHGGGGHGGGHGHGHHHGHGGGHGGHHGGGHGHHHHHGHGGHHGHGHGHGHGHHHGGGHGHGGGGHHHHGGHHGHGGGGHHGHGHHGGHGGGHHHHHGGHGHGHGGHGGHHHGHGGHGHHHHGGHHHHGGHHHHHHGGGHHHGGGGHHGGHGGGGHHGHHHHGHGGGGHGHHHHHHGGGGGGGHHGHHHHGGHGHGGHHHHHHHHHGHGGGGHHGGGGGGGHHGHGHHGHHGHGHHHGHHGGGHHGGGGGHGGHGHHHGGH...

output:

18589853

result:

ok single line: '18589853'

Test #5:

score: 6.25
Accepted
time: 10ms
memory: 32596kb

input:

GHGHGHGHHGGHGGHGHGHGHHGGHHHHHGGGHHGHHHGGHHHHHHHHGHHHHHHGHGHGGHGHGHHHGHGGHGHHHHHGHHHHHGGGHGHHGHGGGGGHHGHGGGHGGGGGHHGHGGHHGGHGHHHGHHHGGHHGHHHHHGGGGHHHHGGGGHGGHHGHHGHHGGGHGHHGHGGGGGHHGHHHHHGHHHHHHGHGGHHHGGGHGHGHGHGHHHGGGGGHHHGHGGHHGGHGGHGHGHHGHGGGHGGGGGGHHHHGGGHGHGGHHGGGHHGGHGHHHHGGGGHGGGHGHGGHHGGGGHGG...

output:

239620295

result:

ok single line: '239620295'

Test #6:

score: 6.25
Accepted
time: 27ms
memory: 63132kb

input:

GHGHHGHHHHHHHGHHGGHHGGHHHGGHHHGGGHHGHGGGHHGGGHGHGHGGHHHHGGGGHGGHHGGHGHHHGGGHHHGHGHHGHHGGHGGGGGHHHHGGGGHGHHHHHGGHGGGGGHGGHHHHGHGHGGHGGGGGGGGHHHGGHHHHGGHHHHGHGGGGHGGHHHHHHHHGGGHHGHGHHHGGGHGHGGGHHHGGHHHGHHHHHHGHGHGHHGHHGHGHHHGHHGGGGHGHGHHGHGHHHGGHGGGGGHGGGHHHHGHGHHHHGHHGGHHHHGHGGHHGGGHGHGHHGHHGHGHHGGGG...

output:

3749745269

result:

ok single line: '3749745269'

Test #7:

score: 0
Dangerous Syscalls

input:

HHHHGGHHHHHHHHGGGHHGHHGHGGHHHGHHGHHHGGGHHHHGHGGGGHGHGGGGHHHHHGHHHGHGHGGGGGGGGHHGHHGGHGHGGGGGHGGHHHHGHHGGHGGHHGGHHGGHGHGGGGHHHGGHGGGHHGGHGGGGGHHHHGHHHGHGGGGGGHGHHHGGHHGHGHHHHHHGHGGHGGHGHGHGGGHGHGHHGHGHGGHGHHHGHGHGHGGHGGHHGHHHGHGGGGGHGGHHHGHHGGGHHGGGHGGHHHHGHHHGGGHGHGGGHGGHGGGHHGGHHGHHHHGHHGHHHGGHHGHH...

output:


result:


Test #8:

score: 0
Dangerous Syscalls

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHGHHHHHHHHHHHGHHHHHHHGGHHHHHHHHHHHHH...

output:


result:


Test #9:

score: 0
Dangerous Syscalls

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHGHHHGHHHHGHHHHHHHHHHHHHHHGHGHHHHHHHHGHHHHHHGHHHHHHHHHHHH...

output:


result:


Test #10:

score: 0
Dangerous Syscalls

input:

HHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHGHHHGHHHHHHHHHHHHHHHHHHHHHHH...

output:


result:


Test #11:

score: 0
Dangerous Syscalls

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHGHGHHHHHHHHHHGHHHHGHHHHHGHGHHHHHHHHHHHHHHHH...

output:


result:


Test #12:

score: 0
Dangerous Syscalls

input:

HHGHGHHGHGHGGHGHGGHGGHHGGGGGGGGGHGHGGGGHHGHGGHGGHGHGGGGGGHGGHHHGHHHGGHGHHHGGHHGGGHHHGGHHGGHHHGHGHHHHHGHGHHHHHGHGGGGHGHHHHHGHHGHGHHHHHGGGGGHGHHGGHGGGHHGHGGHGHHHHGHHGHHHGGHHGGGGGGHGGHHHGHGGHHGGGGHGGGGHHGGHHGGHGGHGGGHHHGGHGHGHGHHGGHGHGGGHHHHGGGHHGHHGHHHHGHGGGHHGHGGGGHHGHHGHHHGHGHHHGHHGGGHGHGHHHHHGHGGGH...

output:


result:


Test #13:

score: 0
Dangerous Syscalls

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH...

output:


result:


Test #14:

score: 0
Dangerous Syscalls

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH...

output:


result:


Test #15:

score: 0
Dangerous Syscalls

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGGHHHHHHHHHHHHHHHGHHHHHHH...

output:


result:


Test #16:

score: 0
Dangerous Syscalls

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHGHHHH...

output:


result: