QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#726439#5473. Move One Coinshstyle#WA 183ms59696kbC++233.9kb2024-11-09 00:40:092024-11-09 00:40:09

Judging History

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

  • [2024-11-09 00:40:09]
  • 评测
  • 测评结果:WA
  • 用时:183ms
  • 内存:59696kb
  • [2024-11-09 00:40:09]
  • 提交

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(){
    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(){
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++) val[i][j]=rnd();
    }
    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: 8ms
memory: 28668kb

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: 0ms
memory: 28844kb

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: 11ms
memory: 34416kb

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

498 498
0 0

result:

ok OK! rot=0

Test #4:

score: 0
Accepted
time: 4ms
memory: 35132kb

input:

500 500
oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 0
498 498

result:

ok OK! rot=0

Test #5:

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

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

497 1
0 499

result:

ok OK! rot=0

Test #6:

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

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 499
497 1

result:

ok OK! rot=0

Test #7:

score: 0
Accepted
time: 13ms
memory: 37040kb

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 498
-498 996

result:

ok OK! rot=3

Test #8:

score: 0
Accepted
time: 9ms
memory: 36492kb

input:

500 500
oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 0
498 498

result:

ok OK! rot=1

Test #9:

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

input:

500 500
xooxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

1 0
-497 -498

result:

ok OK! rot=0

Test #10:

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

input:

500 500
oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 0
498 498

result:

ok OK! rot=0

Test #11:

score: 0
Accepted
time: 4ms
memory: 36676kb

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

498 1
0 499

result:

ok OK! rot=3

Test #12:

score: 0
Accepted
time: 13ms
memory: 36988kb

input:

500 500
oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0 0
498 498

result:

ok OK! rot=1

Test #13:

score: -100
Wrong Answer
time: 183ms
memory: 59696kb

input:

500 500
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo...

output:

353 308
162 35

result:

wrong answer Move-target is not empty