QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#181441#5473. Move One CoinSolitaryDream#WA 94ms17708kbC++202.7kb2023-09-16 19:06:202023-09-16 19:06:21

Judging History

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

  • [2023-09-16 19:06:21]
  • 评测
  • 测评结果:WA
  • 用时:94ms
  • 内存:17708kb
  • [2023-09-16 19:06:20]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
typedef long long ll;
const int N=1005;
const int Mod=1e9+7;
const int bx=23;
const int by=233;
const int INF=1e9;
ll Fast(ll x,int b) {
    b=(b+Mod-1)%(Mod-1);
    ll t=1;
    for(; b; b>>=1,x=x*x%Mod) {
        if(b&1) t=t*x%Mod;
    }
    return t;
}
ll val(int x,int y) {
    return (Fast(bx,x)*Fast(by,y))%Mod;
}
pair<int,int> rot(pair<int,int> p) {
    return {-p.second,p.first};
}
pair<int,int> rotate(pair<int,int> p,int c) {
    while(c--) p=rot(p);
    return p;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<pair<int,int>> A,B;
    int h,w;
    cin >> h >> w;
    FOR(i,0,h-1) {
        string s;
        cin >> s;
        FOR(j,0,w-1) if(s[j]=='o') {
            A.push_back({i,j});
        }
    }
    cin >> h >> w;
    FOR(i,0,h-1) {
        string s;
        cin >> s;
        FOR(j,0,w-1) if(s[j]=='o') {
            B.push_back({i,j});
        }
    }
    if(A.size()==1) {
        cout << A[0].first << ' ' << A[0].second << '\n';
        cout << A[0].first << ' ' << A[0].second << '\n';
        return 0;
    }
    ll u=0;
    int x1=INF,x2=INF,y1=INF,y2=INF;
    for(auto [x,y]: B) {
        // cerr << x << ' ' << y << ' ' << val(x,y) << endl;
        u=(u+val(x,y))%Mod;
        if(x<x1) x2=x1,x1=x;
        else if(x<x2) x2=x;
        if(y<y1) y2=y1,y1=y;
        else if(y<y2) y2=y;
    }
    // cerr << u << endl;
    unordered_map<ll,pair<int,int>> mp;
    for(auto [x,y]: B) {
        ll v=(u+Mod-val(x,y))%Mod;
        int mnx=(x1==x?x2:x1);
        int mny=(y1==y?y2:y1);
        v=v*val(-mnx,0)%Mod;
        v=v*val(0,-mny)%Mod;
        // cerr << v << endl;
        mp[v]={x-mnx,y-mny};
    }
    // cerr << 1+23+23*23+23*23*23 << endl;
    FOR(_,0,3) {
        x1=x2=y1=y2=INF;
        u=0;
        for(auto [x,y]: A) {
            u=(u+val(x,y))%Mod;
            if(x<x1) x2=x1,x1=x;
            else if(x<x2) x2=x;
            if(y<y1) y2=y1,y1=y;
            else if(y<y2) y2=y;
        }
        for(auto [x,y]: A) {
            ll v=(u+Mod-val(x,y))%Mod;
            int mnx=(x1==x?x2:x1);
            int mny=(y1==y?y2:y1);
            v=v*val(-mnx,0)%Mod;
            v=v*val(0,-mny)%Mod;
            if(mp.count(v)) {
                auto [tx,ty]=mp[v];
                tx+=mnx;
                ty+=mny;
                auto r=rotate({x,y},4-_);
                cout << r.second << ' ' << r.first << '\n';
                r=rotate({tx,ty},4-_);
                cout << r.second << ' ' << r.first << '\n';
                return 0;
            }
        }
        for(auto &p: A) p=rot(p);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3508kb

input:

2 3
xox
ooo
4 2
ox
ox
ox
ox

output:

1 0
-1 1

result:

ok OK! rot=1

Test #2:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

3 3
xox
oxo
xox
4 4
oxxx
xxox
xoxo
xxxx

output:

1 2
-1 -1

result:

ok OK! rot=0

Test #3:

score: 0
Accepted
time: 1ms
memory: 3504kb

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

498 498
0 0

result:

ok OK! rot=0

Test #4:

score: 0
Accepted
time: 3ms
memory: 3540kb

input:

500 500
oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 0
498 498

result:

ok OK! rot=0

Test #5:

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

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

497 1
0 499

result:

ok OK! rot=0

Test #6:

score: 0
Accepted
time: 3ms
memory: 3524kb

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 499
497 1

result:

ok OK! rot=0

Test #7:

score: 0
Accepted
time: 3ms
memory: 3540kb

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

1 498
499 0

result:

ok OK! rot=1

Test #8:

score: 0
Accepted
time: 3ms
memory: 3540kb

input:

500 500
oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 0
498 498

result:

ok OK! rot=1

Test #9:

score: 0
Accepted
time: 0ms
memory: 3520kb

input:

500 500
xooxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

1 0
-497 -498

result:

ok OK! rot=0

Test #10:

score: 0
Accepted
time: 3ms
memory: 3536kb

input:

500 500
oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 0
498 498

result:

ok OK! rot=0

Test #11:

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

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

499 1
997 -497

result:

ok OK! rot=1

Test #12:

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

input:

500 500
oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 0
498 498

result:

ok OK! rot=1

Test #13:

score: -100
Wrong Answer
time: 94ms
memory: 17708kb

input:

500 500
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo...

output:

97 12
4 298

result:

wrong answer Move-target is not empty