QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#726447#5473. Move One Coinshstyle#TL 15ms37216kbC++233.9kb2024-11-09 00:44:112024-11-09 00:44:11

Judging History

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

  • [2024-11-09 00:44:11]
  • 评测
  • 测评结果:TL
  • 用时:15ms
  • 内存:37216kb
  • [2024-11-09 00:44:11]
  • 提交

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...

output:


result: