QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#344945 | #4792. Origami | Kevin5307 | WA | 533ms | 88096kb | C++20 | 2.5kb | 2024-03-05 19:53:15 | 2024-03-05 19:53:15 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
using i128=__int128;
void die(string S){puts(S.c_str());exit(0);}
const int maxn=1000005;
const ll mod=(ll)(1e18)+3,base=1e8+3;
ll pw[maxn];
string grid[maxn];
int n,m;
int valRow[maxn],valCol[maxn];
ll L[maxn],R[maxn],H[maxn],Hr[maxn],tmp[maxn];
ll getH(int l,int r)
{
return (H[r+1]-(i128)(H[l])*pw[r-l+1]%mod+mod)%mod;
}
ll getHr(int l,int r)
{
return (Hr[l]-(i128)(Hr[r+1])*pw[r-l+1]%mod+mod)%mod;
}
ll calc(int *v,int n)
{
memset(L,0,sizeof(L));
memset(R,0,sizeof(R));
L[0]=1;
R[n-1]=1;
H[0]=Hr[n]=0;
for(int i=1;i<=n;i++)
H[i]=((i128)(H[i-1])*base+v[i-1])%mod;
for(int i=n-1;i>=0;i--)
Hr[i]=((i128)(Hr[i+1])*base+v[i])%mod;
memset(tmp,0,sizeof(tmp));
tmp[0]=1;
for(int i=1;i<n;i++)
{
int l=0,r=min(i,n-i);
while(l<r)
{
int mid=(l+r+1)/2;
if(getH(i,i+mid-1)!=getHr(i-mid,i-1))
r=mid-1;
else
l=mid;
}
if(l==i)
L[i]=tmp[i-1];
else
L[i]=tmp[i-1]-tmp[i-l-1];
tmp[i]=tmp[i-1]+L[i];
}
memset(tmp,0,sizeof(tmp));
tmp[n-1]=1;
for(int i=n-2;i>=0;i--)
{
int l=0,r=min(n-i-1,i+1);
while(l<r)
{
int mid=(l+r+1)/2;
if(getH(i-mid+1,i)!=getHr(i+1,i+mid))
r=mid-1;
else
l=mid;
}
R[i]=tmp[i+1]-tmp[i+l+1];
tmp[i]=tmp[i+1]+R[i];
}
ll ans=0;
for(int i=0;i<n;i++)
ans+=L[i]*tmp[i];
return ans;
}
int main()
{
pw[0]=1;
for(int i=1;i<maxn;i++)
pw[i]=(i128)(pw[i-1])*base%mod;
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>grid[i];
map<string,int> mpRow,mpCol;
for(int i=0;i<n;i++)
if(mpRow.count(grid[i]))
valRow[i]=mpRow[grid[i]];
else
valRow[i]=mpRow[grid[i]]=sz(mpRow)+1;
for(int i=0;i<m;i++)
{
string str;
for(int j=0;j<n;j++)
str+=grid[j][i];
if(mpCol.count(str))
valCol[i]=mpCol[str];
else
valCol[i]=mpCol[str]=sz(mpCol)+1;
}
cout<<calc(valRow,n)*calc(valCol,m)<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 22ms
memory: 75384kb
input:
5 7 baabbaa cbbccbb ababbab cabccba bccaacc
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: -100
Wrong Answer
time: 533ms
memory: 88096kb
input:
1000000 1 a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ...
output:
-464927327799478656
result:
wrong answer 1st numbers differ - expected: '500000500000', found: '-464927327799478656'