QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#181441 | #5473. Move One Coin | SolitaryDream# | WA | 94ms | 17708kb | C++20 | 2.7kb | 2023-09-16 19:06:20 | 2023-09-16 19:06:21 |
Judging History
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