QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#344945#4792. OrigamiKevin5307WA 533ms88096kbC++202.5kb2024-03-05 19:53:152024-03-05 19:53:15

Judging History

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

  • [2024-03-05 19:53:15]
  • 评测
  • 测评结果:WA
  • 用时:533ms
  • 内存:88096kb
  • [2024-03-05 19:53:15]
  • 提交

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;
}

詳細信息

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'