Submission #35944649

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
ll read(){ll r;scanf("%lld",&r);return r;}
using Arrow=pair<ll,ll>;

namespace MatrixVec{
  // 行列式 高斯消元 解增广矩阵, 答案全为整数
  // {是否成功, 消元后的增广矩阵(左边nxn 为单位矩阵)}
  pair<bool,vector<vector<ll>>> solvell(const vector<vector<ll>>& _a){
    auto a=_a;
    auto n=a.size(); // 行
    if(n==0) return {true,{}};
    assert(n < a[0].size()); // 增广
    rep(j,0,n){
      rep(i,j,n)if(a[i][j]!=0){ // >=j行中找j列首个非零值,做行交换
        if(i!=j) std::swap(a[i],a[j]);
        break;
      }
      if(a[j][j]==0) return {false,{}};
      per(k,j,a[j].size()){ // 保证答案全为整数, 注意顺序
        if(a[j][k] % a[j][j] !=0) return {false,{}};
        a[j][k]/=a[j][j];
      }
      rep(i,0,n) if(i!=j)per(k,j,a[i].size())a[i][k]-=a[i][j]*a[j][k]; // 行变换, 注意per顺序
    }
    return {true,a};
  }
};

vector<Arrow> XY={
  {1,0},
  {1,1},
  {0,1},
  {-1,1},
  {-1,0},
  {-1,-1},
  {0,-1},
  {1,-1},
};

const ll INF=0x3f3f3f3f3f3f3f3f;

char s[10];

ll solve1(Arrow xy,Arrow ab){
  auto [x,y] = xy;
  auto [a,b] = ab;
  if(x*b!=a*y) return INF; // a/x == b/y
  ll res = (x==0?b/y:a/x);
  return res>=0?res:INF;
}

ll solve2(vector<vector<ll>> mat){
  auto [ok,res] = MatrixVec::solvell(mat);
  if(!ok) return INF; // 无整数解
  ll a = res[0][2];
  ll b = res[1][2];
  return (a>=0 && b>=0)?a+b:INF;
}

void w(){
  ll a= read();
  ll b= read();
  scanf("%s",s);
  if(!a && !b) {
    printf("0\n");
    return ;
  }
  vector<Arrow>op;
  rep(i,0,8) if(s[i]=='1') op.push_back(XY[i]);
  ll ans = INF;
  for(auto o:op) ans = min(ans,solve1(o,{a,b}));
  rep(i,0,op.size()) rep(j,i+1,op.size()){
    auto [x0,y0] = op[i];
    auto [x1,y1] = op[j];
    if(x0+x1==0 && y0+y1==0) continue; // 不会取逆向
    ans = min(ans, solve2({
          {x0,x1,a},
          {y0,y1,b},
          }));
  }
  rep(k,0,op.size()){
    auto [x,y] = op[k];
    if(abs(x)+abs(y) != 1) continue; // 使用一次的轴向边
    rep(i,0,op.size()) rep(j,i+1,op.size()){
      auto [x0,y0] = op[i];
      auto [x1,y1] = op[j];
      if(x0+x1==0 && y0+y1==0) continue; // 不会取逆向
      ans = min(ans, 1+solve2({
            {x0,x1,a-x},
            {y0,y1,b-y},
            }));
    }
  }
  printf("%lld\n",ans==INF?-1:ans);
}

int main(){
  int t=read();
  while(t--)w();
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:7:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    7 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~
./Main.cpp: In function ‘void w()’:
./Main.cpp:68:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   68 |   scanf("%s",s);
      |   ~~~~~^~~~~~~~

Judge Result