QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#85824 | #5338. Palindromes | CharlieVinnie | 100 ✓ | 456ms | 151248kb | C++14 | 2.2kb | 2023-03-08 16:28:55 | 2023-03-08 16:28:57 |
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*2],ans[N][N];
int main(){
//~ Fin("hh.in");
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--;
//~ 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--;
//~ 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 6.25
Accepted
time: 2ms
memory: 3408kb
input:
GHHGGHHGH
output:
12
result:
ok single line: '12'
Test #2:
score: 6.25
Accepted
time: 3ms
memory: 7532kb
input:
HHHHHHHHGHGGHGGGGHGGGHGGHGGHGGGGHHHHHGGGGHGHHHGGHGGHHGGHGHGHGHGHGHHHGGHHGHGGHGGGHGGGGHHGGHHHGHHGHHGG
output:
98047
result:
ok single line: '98047'
Test #3:
score: 6.25
Accepted
time: 1ms
memory: 9872kb
input:
GGHHHGHGHHHHGHHHHGHGHGGHHHGHGGHHHGGHGHHGGHHHHGGGHHGGGGHHHGGHGHGHHHGGGGHHHHGGGGGHGHGGGHGGGGHHHGHHHHGGGHGGGHHGGHGHHHHHHGHHHHGGHGHHGHHGHGHHHHHHHGGGHGGHGHGHHGHGHGHHHHGGHGHHGGHHHHGHGHGGHGHHGGHHGHGHHHGGHGHG
output:
1377709
result:
ok single line: '1377709'
Test #4:
score: 6.25
Accepted
time: 0ms
memory: 19784kb
input:
HGGHGHGGGHHHHGGHHGGHHGGHHGHHGHHGHHHGGGGHHGGGGHGGGHGHGHHHGHGGGHGGHHGGGHGHHHHHGHGGHHGHGHGHGHGHHHGGGHGHGGGGHHHHGGHHGHGGGGHHGHGHHGGHGGGHHHHHGGHGHGHGGHGGHHHGHGGHGHHHHGGHHHHGGHHHHHHGGGHHHGGGGHHGGHGGGGHHGHHHHGHGGGGHGHHHHHHGGGGGGGHHGHHHHGGHGHGGHHHHHHHHHGHGGGGHHGGGGGGGHHGHGHHGHHGHGHHHGHHGGGHHGGGGGHGGHGHHHGGH...
output:
18589853
result:
ok single line: '18589853'
Test #5:
score: 6.25
Accepted
time: 12ms
memory: 32688kb
input:
GHGHGHGHHGGHGGHGHGHGHHGGHHHHHGGGHHGHHHGGHHHHHHHHGHHHHHHGHGHGGHGHGHHHGHGGHGHHHHHGHHHHHGGGHGHHGHGGGGGHHGHGGGHGGGGGHHGHGGHHGGHGHHHGHHHGGHHGHHHHHGGGGHHHHGGGGHGGHHGHHGHHGGGHGHHGHGGGGGHHGHHHHHGHHHHHHGHGGHHHGGGHGHGHGHGHHHGGGGGHHHGHGGHHGGHGGHGHGHHGHGGGHGGGGGGHHHHGGGHGHGGHHGGGHHGGHGHHHHGGGGHGGGHGHGGHHGGGGHGG...
output:
239620295
result:
ok single line: '239620295'
Test #6:
score: 6.25
Accepted
time: 31ms
memory: 61380kb
input:
GHGHHGHHHHHHHGHHGGHHGGHHHGGHHHGGGHHGHGGGHHGGGHGHGHGGHHHHGGGGHGGHHGGHGHHHGGGHHHGHGHHGHHGGHGGGGGHHHHGGGGHGHHHHHGGHGGGGGHGGHHHHGHGHGGHGGGGGGGGHHHGGHHHHGGHHHHGHGGGGHGGHHHHHHHHGGGHHGHGHHHGGGHGHGGGHHHGGHHHGHHHHHHGHGHGHHGHHGHGHHHGHHGGGGHGHGHHGHGHHHGGHGGGGGHGGGHHHHGHGHHHHGHHGGHHHHGHGGHHGGGHGHGHHGHHGHGHHGGGG...
output:
3749745269
result:
ok single line: '3749745269'
Test #7:
score: 6.25
Accepted
time: 185ms
memory: 115692kb
input:
HHHHGGHHHHHHHHGGGHHGHHGHGGHHHGHHGHHHGGGHHHHGHGGGGHGHGGGGHHHHHGHHHGHGHGGGGGGGGHHGHHGGHGHGGGGGHGGHHHHGHHGGHGGHHGGHHGGHGHGGGGHHHGGHGGGHHGGHGGGGGHHHHGHHHGHGGGGGGHGHHHGGHHGHGHHHHHHGHGGHGGHGHGHGGGHGHGHHGHGHGGHGHHHGHGHGHGGHGGHHGHHHGHGGGGGHGGHHHGHHGGGHHGGGHGGHHHHGHHHGGGHGHGGGHGGHGGGHHGGHHGHHHHGHHGHHHGGHHGHH...
output:
81813329996
result:
ok single line: '81813329996'
Test #8:
score: 6.25
Accepted
time: 148ms
memory: 113144kb
input:
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHGHHHHHHHHHHHGHHHHHHHGGHHHHHHHHHHHHH...
output:
1993575766369
result:
ok single line: '1993575766369'
Test #9:
score: 6.25
Accepted
time: 151ms
memory: 112528kb
input:
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHGHHHGHHHHGHHHHHHHHHHHHHHHGHGHHHHHHHHGHHHHHHGHHHHHHHHHHHH...
output:
1936319118814
result:
ok single line: '1936319118814'
Test #10:
score: 6.25
Accepted
time: 160ms
memory: 112980kb
input:
HHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHGHHHGHHHHHHHHHHHHHHHHHHHHHHH...
output:
1906624646754
result:
ok single line: '1906624646754'
Test #11:
score: 6.25
Accepted
time: 144ms
memory: 112588kb
input:
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHGHGHHHHHHHHHHGHHHHGHHHHHGHGHHHHHHHHHHHHHHHH...
output:
2056784748165
result:
ok single line: '2056784748165'
Test #12:
score: 6.25
Accepted
time: 456ms
memory: 150852kb
input:
HHGHGHHGHGHGGHGHGGHGGHHGGGGGGGGGHGHGGGGHHGHGGHGGHGHGGGGGGHGGHHHGHHHGGHGHHHGGHHGGGHHHGGHHGGHHHGHGHHHHHGHGHHHHHGHGGGGHGHHHHHGHHGHGHHHHHGGGGGHGHHGGHGGGHHGHGGHGHHHHGHHGHHHGGHHGGGGGGHGGHHHGHGGHHGGGGHGGGGHHGGHHGGHGGHGGGHHHGGHGHGHGHHGGHGHGGGHHHHGGGHHGHHGHHHHGHGGGHHGHGGGGHHGHHGHHHGHGHHHGHHGGGHGHGHHHHHGHGGGH...
output:
516066376178
result:
ok single line: '516066376178'
Test #13:
score: 6.25
Accepted
time: 350ms
memory: 151112kb
input:
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH...
output:
9878475549129
result:
ok single line: '9878475549129'
Test #14:
score: 6.25
Accepted
time: 352ms
memory: 150572kb
input:
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH...
output:
9918848392027
result:
ok single line: '9918848392027'
Test #15:
score: 6.25
Accepted
time: 341ms
memory: 150440kb
input:
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGGHHHHHHHHHHHHHHHGHHHHHHH...
output:
9882416063183
result:
ok single line: '9882416063183'
Test #16:
score: 6.25
Accepted
time: 348ms
memory: 151248kb
input:
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHGHHHH...
output:
9847097832382
result:
ok single line: '9847097832382'