QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#338604#5473. Move One Coinleo020630WA 4ms6352kbC++174.8kb2024-02-26 03:31:012024-02-26 03:31:02

Judging History

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

  • [2024-02-26 03:31:02]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:6352kb
  • [2024-02-26 03:31:01]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef pair<long double,long double> pdd;
typedef long double ld;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

using namespace std;

pii operator+(const pii &a, const pii &b) {
    return {a.fi+b.fi,a.se+b.se};
}
pii operator-(const pii &a, const pii &b) {
    return {a.fi-b.fi,a.se-b.se};
}
vector<string> A,B;
bool dp[250005][3][4];
tuple<int,int,int> prv[250005][3][4];
bool match()
{
    vector<pii> vA,vB;
    int n1=A.size(),m1=A[0].size(),n2=B.size(),m2=B[0].size();
    for(int i=0;i<n1;i++) for(int j=0;j<m1;j++) if(A[i][j]=='o') vA.push_back({i,j});
    for(int i=0;i<n2;i++) for(int j=0;j<m2;j++) if(B[i][j]=='o') vB.push_back({i,j});
    if(vA.size()==1)
    {
        cout<<vA[0].se<<' '<<vA[0].fi<<'\n';
        cout<<vA[0].se<<' '<<vA[0].fi<<'\n';
        return 1;
    }
    vector<pii> mA,mB;
    for(int i=1;i<vA.size();i++) mA.push_back(vA[i]-vA[i-1]);
    for(int i=1;i<vB.size();i++) mB.push_back(vB[i]-vB[i-1]);
    if(mA==mB)
    {
        cout<<vA[0].se<<' '<<vA[0].fi<<'\n';
        cout<<vA[0].se<<' '<<vA[0].fi<<'\n';
        return 1;
    }
    //cout<<"HI22222\n";
    dp[0][1][0]=dp[0][2][1]=1;
    prv[0][2][1]={0,1,0};
    for(int i=1;i<=mA.size();i++) for(int j=0;j<=2;j++) for(int k=0;k<4;k++)
    {
        if(j==2&&i==mA.size()) continue;
        dp[i][j][k]=0;
        if(i==1&&j==0)
        {
            if(k!=2) dp[i][j][k]=0;
            else dp[i][j][k]=1, prv[i][j][k]={0,1,0};
        }
        else
        {
            if(j==0)
            {
                if(dp[i-1][0][k]&&mA[i-1]==mB[i-2]) dp[i][j][k]=1, prv[i][j][k]={i-1,0,k};
                if(mA[i-2]+mA[i-1]==mB[i-2]&&k>=2&&dp[i-2][1][k-2]) dp[i][j][k]=1, prv[i][j][k]={i-2,1,k-2};
            }
            else if(j==1)
            {
                if(dp[i-1][1][k]&&mA[i-1]==mB[i-1]) dp[i][j][k]=1, prv[i][j][k]={i-1,1,k};
                if(mA[i-2]+mA[i-1]==mB[i-1]&&k>=2&&dp[i-2][2][k-2]) dp[i][j][k]=1, prv[i][j][k]={i-2,2,k-2};
                if(mB[i-2]+mB[i-1]==mA[i-1]&&k%2==1&&dp[i-1][0][k-1]) dp[i][j][k]=1, prv[i][j][k]={i-1,0,k-1};
                if(i>=2&&mB[i-2]+mB[i-1]==mA[i-2]+mA[i-1]&&k==3&&dp[i-2][1][0]) dp[i][j][k]=1, prv[i][j][k]={i-2,1,0};
            }
            else
            {
                if(dp[i-1][2][k]&&mA[i-1]==mB[i]) dp[i][j][k]=1, prv[i][j][k]={i-1,2,k};
                if(mB[i-1]+mB[i]==mA[i-1]&&k%2==1&&dp[i-1][1][k-1]) dp[i][j][k]=1, prv[i][j][k]={i-1,1,k-1};
            }

            if(i==mA.size()&&j==1)
            {
                if(k>=2&&dp[i-1][2][k-2]) dp[i][j][k]=1, prv[i][j][k]={i-1,2,k-2};
                if(k%2==1&&dp[i][0][k-1]) dp[i][j][k]=1, prv[i][j][k]={i,0,k-1};
                if(k==3&&dp[i-1][1][0]) dp[i][j][k]=1, prv[i][j][k]={i-1,1,0};
            }
        }
    }
    //for(int i=0;i<mA.size();i++) cout<<mA[i].fi<<' '<<mA[i].se<<'\n';
    //for(int i=0;i<mB.size();i++) cout<<mB[i].fi<<' '<<mB[i].se<<'\n';
    //for(int i=1;i<=mA.size();i++) for(int j=0;j<=2;j++) for(int k=0;k<4;k++) cout<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k]<<'\n';
    //cout<<'\n';
    //cout<<"HI33333\n";
    if(!dp[mA.size()][1][3]) return 0;
    int i=mA.size(),j=1,k=3,x,y;
    while(i!=0||j!=1)
    {
        //cout<<"FUCKYOU\n";
        int ii,jj,kk;
        tie(ii,jj,kk)=prv[i][j][k];
        //cout<<i<<' '<<j<<' '<<k<<'\n';
        //cout<<ii<<' '<<jj<<' '<<kk<<'\n';
        if(kk+2<=k)
        {
            if(ii==i-2) x=i-1;
            else if(i==mA.size()) x=mA.size();
            else x=0;
        }
        if(kk%2!=k%2)
        {
            int jp=i+j-1,jjp=ii+jj-1;
            if(jp-2==jjp) y=jp-1;
            else if(jp==mA.size()) y=mA.size();
            else y=0;
        }
        i=ii; j=jj; k=kk;
    }
    //cout<<"HIHIHIHIIHI\n";
    int xx=(x==0?1:0), yy=(y==0?1:0);
    pii minus=vA[xx]-vB[yy];
    cout<<vA[x].se<<' '<<vA[x].fi<<'\n';
    cout<<vB[y].se+minus.se<<' '<<vB[y].fi+minus.fi<<'\n';
    return 1;
}
void spin()
{
    vector<string> C;
    int n=B[0].size(),m=B.size();
    C.resize(n);
    for(int i=0;i<n;i++) C[i].resize(m);
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
        C[n-1-i][j]=B[j][i];
    B=C;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n1,m1,n2,m2;
    cin>>n1>>m1; A.resize(n1);
    for(int i=0;i<n1;i++) cin>>A[i];
    cin>>n2>>m2; B.resize(n2);
    for(int i=0;i<n2;i++) cin>>B[i];
    //cout<<"HI\n";
    bool flag=0;
    for(int t=0;t<4;t++)
    {
        if(match()) break;
        spin();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5828kb

input:

2 3
xox
ooo
4 2
ox
ox
ox
ox

output:

1 0
3 1

result:

ok OK! rot=1

Test #2:

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

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: 3ms
memory: 6352kb

input:

500 500
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

498 499
996 997

result:

ok OK! rot=2

Test #4:

score: -100
Wrong Answer
time: 4ms
memory: 6304kb

input:

500 500
oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:


result:

wrong output format Unexpected end of file - int32 expected