Submission #1353750

#TimeUsernameProblemLanguageResultExecution timeMemory
1353750Francisco_MartinSuperpiece (EGOI22_superpiece)C++20
100 / 100
2 ms344 KiB
//EGOI 2022 Superpiece
//https://qoj.ac/contest/2260/problem/5183

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using pll = pair<ll,ll>;

set<pll> movesN={{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};
set<pll> movesK={{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1}}, movesP={{1,0}};

ll disB(ll x,ll y,bool flag){
    if(!flag) return 1e18;
    return ((x+y==0 || x-y==0)?1:((x+y)%2==0)?2:1e18);
}
ll disN(ll x,ll y,bool flag){
    if(!flag) return 1e18;
    x=abs(x); y=abs(y); 
    if(x<y) swap(x,y);
    if(x==1 && y==0) return 3;
    if(x==2 && y==2) return 4;
    if(x==1 && y==1) return 2;
    ll res=max((x+1)/2,(x+y+2)/3); res+=(res%2!=(x+y)%2);
    return res;
}
ll disK(ll x,ll y,bool flag){
    if(!flag) return 1e18;
    return max(abs(x),abs(y));
}
ll disP(ll x,ll y, bool flag){
    if(!flag) return 1e18;
    return ((x>=0 && y==0)?x:1e18);
}

void solve(){
    ll a, b, c, d, ans=1e18; string s; bool Q, R, B, N, K, P;
    cin >> s >> a >> b >> c >> d;
    Q=R=B=N=K=P=false; ll x=c-a, y=d-b;
    for(auto c:s){
        Q|=(c=='Q'); R|=(c=='R'); B|=(c=='B');
        N|=(c=='N'); K|=(c=='K'); P|=(c=='P');
    }
    if((x==0 || y==0) && (Q || R)){cout << "1\n"; return;}
    if((x+y==0 || x-y==0) && (Q || B)){cout << "1\n"; return;}
    if((movesN.count({x,y}) && N) || (movesK.count({x,y}) && K) || (movesP.count({x,y}) && P)){
        cout << "1\n"; return;
    }
    if(Q || R){cout << "2\n"; return;}
    ans=min({ans,disB(x,y,B),disN(x,y,N),disK(x,y,K),disP(x,y,P)});
    if(N) for(auto [a,b]:movesN) ans=min({ans,disB(x-a,y-b,B)+1,disK(x-a,y-b,K)+1,disP(x-a,y-b,P)+1});
    if(K) for(auto [a,b]:movesK) ans=min({ans,disB(x-a,y-b,B)+1,disN(x-a,y-b,N)+1,disP(x-a,y-b,P)+1});
    if(P) for(auto [a,b]:movesP) ans=min({ans,disB(x-a,y-b,B)+1,disN(x-a,y-b,N)+1,disK(x-a,y-b,K)+1});
    cout << (ans==1e18?-1:ans) << "\n";
}

int main(){
    ll tt;
    cin >> tt;
    while(tt--) solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...