QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#726447 | #5473. Move One Coin | shstyle# | TL | 15ms | 37216kb | C++23 | 3.9kb | 2024-11-09 00:44:11 | 2024-11-09 00:44:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int N=1010,mod=998244353;
int n,m,nn,mm;
char s[N][N],s2[N][N];
int a[N][N],b[N][N],tmp[N][N];
ll val[N][N];
ll ha[N][N],hb[N][N];
mt19937 rnd(time(0));
void move(){
for(int i=0;i<mm;i++){
for(int j=0;j<nn;j++){
tmp[i][j]=b[j][mm-1-i];
}
}
swap(nn,mm);
for(int i=0;i<nn;i++){
for(int j=0;j<mm;j++){
b[i][j]=tmp[i][j];
// cout<<b[i][j]<<" ";
}
// cout<<endl;
}
}
ll cal(vector<PII> &v){
ll mnx=1e9,mny=1e9;
for(auto [x,y]:v){
mnx=min(mnx,x);
mny=min(mny,y);
}
ll ans=0;
for(auto [x,y]:v) ans^=val[x-mnx][y-mny];
return ans;
}
PII calans(){
PII zb1={-1,-1},zb2={-1,-1};
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(a[i][j]==1){
zb1={i,j};
break;
}
}
if(zb1.first!=-1) break;
}
for(int i=0;i<nn;i++){
for(int j=0;j<mm;j++){
if(b[i][j]==1){
zb2={i,j};
break;
}
}
if(zb2.first!=-1) break;
}
return {zb1.first-zb2.first,zb1.second-zb2.second};
}
void check(){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++) val[i][j]=rnd();
}
memset(hb,-1,sizeof hb);
map<ll,PII> mp;
{
map<int,int> cx,cy;
vector<PII> zb;
int mnx=1e9,mny=1e9;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(a[i][j]){
zb.push_back({i,j});
mnx=min(mnx,i);
mny=min(mny,j);
}
}
}
for(auto &[x,y]:zb){
x-=mnx,y-=mny;
cx[x]++,cy[y]++;
}
ll base=cal(zb);
for(int i=0;i<zb.size();i++){
int x=zb[i].first,y=zb[i].second;
// if((x==0&&cx[0]==1)||(y==0&&cy[0]==1))
// {
vector<PII> v2;
for(int j=0;j<zb.size();j++) if(i!=j) v2.push_back(zb[j]);
ha[x+mnx][y+mny]=cal(v2);
// }else{
// ha[x+mnx][y+mny]=base^val[x][y];
// }
mp[ha[x+mnx][y+mny]]={x+mnx,y+mny};
}
}
{
map<int,int> cx,cy;
vector<PII> zb;
int mnx=1e9,mny=1e9;
for(int i=0;i<nn;i++){
for(int j=0;j<mm;j++){
if(b[i][j]){
zb.push_back({i,j});
mnx=min(mnx,i);
mny=min(mny,j);
}
}
}
for(auto &[x,y]:zb){
x-=mnx,y-=mny;
cx[x]++,cy[y]++;
}
ll base=cal(zb);
for(int i=0;i<zb.size();i++){
int x=zb[i].first,y=zb[i].second;
if((x==0&&cx[0]==1)||(y==0&&cy[0]==1))
{
vector<PII> v2;
for(int j=0;j<zb.size();j++) if(i!=j) v2.push_back(zb[j]);
hb[x+mnx][y+mny]=cal(v2);
}else{
hb[x+mnx][y+mny]=base^val[x][y];
}
// mp[ha[x+mnx][y+mny]]={x+mnx,y+mny};
}
}
for(int i=0;i<nn;i++){
for(int j=0;j<mm;j++){
if(hb[i][j]==-1) continue;
if(!mp.count(hb[i][j])) continue;
PII ans=mp[hb[i][j]];
// cout<<i<<" "<<j<<endl;
cout<<ans.second<<" "<<ans.first<<endl;
a[ans.first][ans.second]=0;
b[i][j]=0;
ans=calans();
cout<<j+ans.second<<" "<<i+ans.first<<endl;
exit(0);
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) scanf("%s",s[i]);
cin>>nn>>mm;
for(int i=0;i<nn;i++){
scanf("%s",s2[i]);
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(s[i][j]=='o') a[i][j]=1;
else a[i][j]=0;
}
}
for(int i=0;i<nn;i++){
for(int j=0;j<mm;j++){
if(s2[i][j]=='o') b[i][j]=1;
else b[i][j]=0;
}
}
check();
move();
check();
move();
check();
move();
check();
move();
}
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 31568kb
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: 4ms
memory: 28908kb
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: 0ms
memory: 35100kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
498 498 0 0
result:
ok OK! rot=0
Test #4:
score: 0
Accepted
time: 4ms
memory: 34968kb
input:
500 500 oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 0 498 498
result:
ok OK! rot=0
Test #5:
score: 0
Accepted
time: 8ms
memory: 33196kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
497 1 0 499
result:
ok OK! rot=0
Test #6:
score: 0
Accepted
time: 8ms
memory: 34856kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 499 497 1
result:
ok OK! rot=0
Test #7:
score: 0
Accepted
time: 8ms
memory: 36988kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 498 -498 996
result:
ok OK! rot=3
Test #8:
score: 0
Accepted
time: 15ms
memory: 37064kb
input:
500 500 oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 0 498 498
result:
ok OK! rot=1
Test #9:
score: 0
Accepted
time: 3ms
memory: 32684kb
input:
500 500 xooxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
1 0 -497 -498
result:
ok OK! rot=0
Test #10:
score: 0
Accepted
time: 3ms
memory: 34936kb
input:
500 500 oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 0 498 498
result:
ok OK! rot=0
Test #11:
score: 0
Accepted
time: 8ms
memory: 36604kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
498 1 0 499
result:
ok OK! rot=3
Test #12:
score: 0
Accepted
time: 8ms
memory: 37216kb
input:
500 500 oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 0 498 498
result:
ok OK! rot=1
Test #13:
score: -100
Time Limit Exceeded
input:
500 500 oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo...