QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#170548 | #5473. Move One Coin | PhantomThreshold# | WA | 15ms | 15564kb | C++20 | 4.1kb | 2023-09-09 15:30:33 | 2023-09-09 15:30:34 |
Judging History
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