QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#338604 | #5473. Move One Coin | leo020630 | WA | 4ms | 6352kb | C++17 | 4.8kb | 2024-02-26 03:31:01 | 2024-02-26 03:31:02 |
Judging History
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