QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#85818 | #5338. Palindromes | CharlieVinnie | 37.5 | 27ms | 63132kb | C++14 | 2.1kb | 2023-03-08 16:16:09 | 2023-03-08 16:16:11 |
Judging History
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...