QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#170548#5473. Move One CoinPhantomThreshold#WA 15ms15564kbC++204.1kb2023-09-09 15:30:332023-09-09 15:30:34

Judging History

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

  • [2023-09-09 15:30:34]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:15564kb
  • [2023-09-09 15:30:33]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int maxn=1000;


typedef long long ll;
const ll bx1=17;
const ll by1=19;
const ll mod1=993244853;
const ll bx2=107;
const ll by2=109;
const ll mod2=1000000009;
ll ksm(ll a,ll x,ll mod){
	ll ret=1;
	for (;x;x>>=1,a=a*a%mod) if (x&1) ret=ret*a%mod;
	return ret;
}
ll inv(ll a,ll mod){return ksm(a,mod-2,mod);}

void pre(ll x,ll mod,ll pw[],ll ipw[]){
	pw[0]=1;
	for (int i=1;i<=maxn;i++) pw[i]=pw[i-1]*x%mod;
	ipw[maxn]=inv(pw[maxn],mod);
	for (int i=maxn-1;i>=0;i--) ipw[i]=ipw[i+1]*x%mod;
}
ll pwx1[maxn+50];
ll pwy1[maxn+50];
ll pwx2[maxn+50];
ll pwy2[maxn+50];
ll ipwx1[maxn+50];
ll ipwy1[maxn+50];
ll ipwx2[maxn+50];
ll ipwy2[maxn+50];
void prepare(){
	pre(bx1,mod1,pwx1,ipwx1);
	pre(by1,mod1,pwy1,ipwy1);
	pre(bx2,mod2,pwx2,ipwx2);
	pre(by2,mod2,pwy2,ipwy2);
}

void add(pair<ll,ll> &h,ll i,ll j){
	h.first =(h.first +pwx1[i]*pwy1[j])%mod1;
	h.second=(h.second+pwx2[i]*pwy2[j])%mod2;
}
void sub(pair<ll,ll> &h,ll i,ll j){
	h.first =(h.first -pwx1[i]*pwy1[j])%mod1;
	h.second=(h.second-pwx2[i]*pwy2[j])%mod2;
	if (h.first <0) h.first +=mod1;
	if (h.second<0) h.second+=mod2;
}
void shl(pair<ll,ll> &h,ll i,ll j){
	h.first =h.first *ipwx1[i]%mod1*ipwy1[j]%mod1;
	h.second=h.second*ipwx2[i]%mod2*ipwy2[j]%mod2;
}

ll getid(const pair<ll,ll> &h){
	return (h.first<<32)|(h.second);	
}

int h,w;
int a[maxn+5][maxn+5];
int H,W;
int b[maxn+5][maxn+5];



void gao(){
	/*
	cerr << "------------" << endl;
	cerr << h << " " << w << endl;
	for (int i=1;i<=h;i++){
		for (int j=1;j<=w;j++){
			cerr << a[i][j];
		}
		cerr << endl;
	}
	cerr << "------------" << endl;
	cerr << H << " " << W << endl;
	for (int i=1;i<=H;i++){
		for (int j=1;j<=W;j++){
			cerr << b[i][j];
		}
		cerr << endl;
	}
	*/
	unordered_map<ll,pair<ll,ll>> dict;
	{
		pair<ll,ll> hv(0LL,0LL);
		set<pair<int,int>> s1,s2;
		for (int i=1;i<=H;i++){
			for (int j=1;j<=W;j++){
				if (b[i][j]==0) continue;
				add(hv,i,j);
				s1.emplace(i,j);
				s2.emplace(j,i);
			}
		}
		for (int i=1;i<=H;i++){
			for (int j=1;j<=W;j++){
				if (b[i][j]==0) continue;
				s1.erase(make_pair(i,j));
				s2.erase(make_pair(j,i));
				ll dx=s1.begin()->first;
				ll dy=s2.begin()->first;
				
				pair<ll,ll> tmp=hv;
				sub(tmp,i,j);
				shl(tmp,dx,dy);
				dict[getid(tmp)]=make_pair(i-dx,j-dy);
				
				s1.emplace(i,j);
				s2.emplace(j,i);
			}
		}
	}
	{
		pair<ll,ll> hv(0LL,0LL);
		set<pair<int,int>> s1,s2;
		for (int i=1;i<=h;i++){
			for (int j=1;j<=w;j++){
				if (a[i][j]==0) continue;
				add(hv,i,j);
				s1.emplace(i,j);
				s2.emplace(j,i);
			}
		}
		for (int i=1;i<=h;i++){
			for (int j=1;j<=w;j++){
				if (a[i][j]==0) continue;
				s1.erase(make_pair(i,j));
				s2.erase(make_pair(j,i));
				ll dx=s1.begin()->first;
				ll dy=s2.begin()->first;
				
				pair<ll,ll> tmp=hv;
				sub(tmp,i,j);
				shl(tmp,dx,dy);
				
				s1.emplace(i,j);
				s2.emplace(j,i);
				
				ll id=getid(tmp);
				if (dict.count(id)==0) continue;
				auto tt=dict[id];
				ll dirx=tt.first;
				ll diry=tt.second;
				if (i==dx+dirx && j==dy+diry) continue;
				cout << j-1 << " " << i-1 << "\n";
				cout << dy+diry-1 << " " << dx+dirx-1 << "\n";
				exit(0);
			}
		}
	}
}

string str;
int tmp[maxn+5][maxn+5];

int main(){
	prepare();
	int cnt=0,posx=0,posy=0;
	cin >> h >> w;
	for (int i=1;i<=h;i++){
		cin >> str;
		for (int j=1;j<=w;j++){
			a[i][j]=(str[j-1]=='o');
			if (a[i][j]){
				cnt++;
				posx=i;
				posy=j;	
			}
		}
	}
	cin >> H >> W;
	for (int i=1;i<=H;i++){
		cin >> str;
		for (int j=1;j<=W;j++) b[i][j]=(str[j-1]=='o');	
	}
	
	if (cnt==1){
		cout << posy-1 << " " << posx-1 << "\n";
		cout << posy << " " << posx << "\n";
		return 0;	
	}
	
	for (int DIR=0;DIR<4;DIR++){
		if (DIR==1){
			gao();
		}
		//rotate
		for (int i=1;i<=H;i++){
			for (int j=1;j<=W;j++){
				tmp[W-j+1][i]=b[i][j];
				b[i][j]=0;
			}
		}
		swap(W,H);
		for (int i=1;i<=H;i++){
			for (int j=1;j<=W;j++){
				b[i][j]=tmp[i][j];
			}
		}
	}
	return 0;	
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 7800kb

input:

2 3
xox
ooo
4 2
ox
ox
ox
ox

output:

1 0
3 1

result:

ok OK! rot=1

Test #2:

score: 0
Accepted
time: 2ms
memory: 7804kb

input:

3 3
xox
oxo
xox
4 4
oxxx
xxox
xoxo
xxxx

output:

2 1
-1 3

result:

ok OK! rot=3

Test #3:

score: -100
Wrong Answer
time: 15ms
memory: 15564kb

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:


result:

wrong output format Unexpected end of file - int32 expected