#2117 (C++11) No.62 リベリオン(Extra)

提出ソース
結果

問題	No.62 リベリオン(Extra)
ユーザー	LayCurse
提出日時	2014-11-10 09:02:26
言語	C++11 (gcc 11.4.0)
結果	WA
実行時間	-
コード長	9,447 bytes
コンパイル時間	2,248 ms
コンパイル使用メモリ	169,048 KB
実行使用メモリ	6,940 KB
最終ジャッジ日時	2024-06-10 02:17:41
合計ジャッジ時間	2,462 ms
ジャッジサーバーID （参考情報）	judge1 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	1 ms 6,940 KB
testcase_02	AC	13 ms 6,940 KB
testcase_03	AC	14 ms 6,940 KB
testcase_04	WA	-
権限があれば一括ダウンロードができます
ソースコード

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

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long

#define BIG_INT_SIZE 10
#define BIG_INT_BASE 100000000LL
#define BIG_INT_DIGITS 8
#define BIG_INT_CHAR_SIZE 1000 /* BIG_INT_SIZE*BIG_INT_DIGITS+2以上 */

typedef struct big_integer{ll a[BIG_INT_SIZE];}bigInt;

int bigIntSign(bigInt a);
int bigIntToChar(bigInt a,char ret[]);
void printBigInt(bigInt a);
void putBigInt(bigInt a);


bigInt bigIntZero(){
  bigInt a; int i;
  rep(i,BIG_INT_SIZE) a.a[i]=0;
  return a;
}

bigInt bigIntOne(){
  bigInt a; int i;
  REP(i,1,BIG_INT_SIZE) a.a[i]=0; a.a[0]=1;
  return a;
}

bigInt bigIntOrder(bigInt a){
  int i; ll k;
  REP(i,1,BIG_INT_SIZE) if(a.a[i-1]<0 || a.a[i-1]>=BIG_INT_BASE){
    k=a.a[i-1]/BIG_INT_BASE; a.a[i-1]-=k*BIG_INT_BASE;
    if(a.a[i-1]<0) k--, a.a[i-1]+=BIG_INT_BASE; a.a[i]+=k;
  }
  if(a.a[BIG_INT_SIZE-1]<0){
    rep(i,BIG_INT_SIZE) a.a[i]=-a.a[i]; a=bigIntOrder(a);
    rep(i,BIG_INT_SIZE) a.a[i]=-a.a[i];
  }
  return a;
}

bigInt llToBigInt(ll a){
  bigInt c; int i;
  REP(i,1,BIG_INT_SIZE) c.a[i]=0; c.a[0]=a;
  return bigIntOrder(c);
}

int bigIntGreaterThan(bigInt a,bigInt b){
  int i;
  for(i=BIG_INT_SIZE-1;i>=0;i--){
    if(a.a[i]>b.a[i]) return 1;
    if(a.a[i]<b.a[i]) return 0;
  }
  return 0;
}

int bigIntIsZero(bigInt a){
  int i; rep(i,BIG_INT_SIZE) if(a.a[i]) return 0; return 1;
}

bigInt bigIntPlus(bigInt a,bigInt b){
  int i; bigInt c;
  rep(i,BIG_INT_SIZE) c.a[i]=a.a[i]+b.a[i];
  return bigIntOrder(c);
}

bigInt bigIntMinus(bigInt a,bigInt b){
  int i; bigInt c;
  rep(i,BIG_INT_SIZE) c.a[i]=a.a[i]-b.a[i];
  return bigIntOrder(c);
}

bigInt bigIntMultipleLL(bigInt a,ll b){
  int i; rep(i,BIG_INT_SIZE) a.a[i]*=b;
  return bigIntOrder(a);
}

bigInt bigIntPlusSimple(bigInt a,bigInt b){
  int i; bigInt c;
  rep(i,BIG_INT_SIZE) c.a[i]=a.a[i]+b.a[i];
  return c;
}

bigInt bigIntMinusSimple(bigInt a,bigInt b){
  int i; bigInt c;
  rep(i,BIG_INT_SIZE) c.a[i]=a.a[i]-b.a[i];
  return c;
}

bigInt bigIntMultipleLLSimple(bigInt a,ll b){
  int i; rep(i,BIG_INT_SIZE) a.a[i]*=b;
  return a;
}

bigInt bigIntMultiple(bigInt a,bigInt b){
  int i,j,ii,jj; bigInt c;
  for(ii=BIG_INT_SIZE-1;ii;ii--) if(a.a[ii]) break; ii++;
  if(ii==1) return bigIntMultipleLL(b,a.a[0]);
  for(jj=BIG_INT_SIZE-1;jj;jj--) if(b.a[jj]) break; jj++;
  if(jj==1) return bigIntMultipleLL(a,b.a[0]);
  rep(i,BIG_INT_SIZE) c.a[i]=0;
  rep(i,ii)if(a.a[i])for(j=0;j<jj&&i+j+1<BIG_INT_SIZE;j++) c.a[i+j]+=a.a[i]*b.a[j];
  return bigIntOrder(c);
}

void bigIntDivisionsLL(bigInt a,ll b,bigInt *c,ll *d){
  int i;
  rep(i,BIG_INT_SIZE) c->a[i]=a.a[i];
  for(i=BIG_INT_SIZE-1;i;i--)
    c->a[i-1]+=(c->a[i]%b)*BIG_INT_BASE, c->a[i]/=b;
  *d = c->a[0]%b; c->a[0]/=b;
}

/* c=a/b, d=a%b */
void bigIntDivisions(bigInt a,bigInt b,bigInt *c,bigInt *d){
  int i,j,s,sa,sb; ll ma,mb,mc; bigInt tmp;
  sa=bigIntSign(a); sb=bigIntSign(b);
  if(sa==-1) a=bigIntMultipleLL(a,-1);
  if(sb==-1) b=bigIntMultipleLL(b,-1);
  
  for(j=BIG_INT_SIZE-1;j;j--) if(b.a[j]) break;
  if(!j){
    REP(i,1,BIG_INT_SIZE) d->a[i]=0;
    bigIntDivisionsLL(a,b.a[0],c,&(d->a[0]));
  }else{
    for(i=BIG_INT_SIZE-1;i;i--) if(a.a[i]) break;
    s=i-j; if(s<0) s=0;
    rep(i,BIG_INT_SIZE) c->a[i]=0;
    while(s>=0){
      ma=0; mb=BIG_INT_BASE-1;
      while(ma!=mb){
        mc = (ma+mb)/2 + (ma+mb)%2;
        c->a[s]=mc; tmp=bigIntMultiple(*c,b);
        if(bigIntGreaterThan(tmp,a)) mb=mc-1; else ma=mc;
      }
      c->a[s]=ma; s--;
    }
    tmp = bigIntMultiple(b,*c);
    *d = bigIntMinus(a,tmp);
  }

  if(sa==-1 && sb==-1){
    *d=bigIntMultipleLL(*d,-1);
  } else if(sa==-1 && sb!=-1){
    *c=bigIntMultipleLL(*c,-1);
    *d=bigIntMultipleLL(*d,-1);
  } else if(sa!=-1 && sb==-1){
    *c=bigIntMultipleLL(*c,-1);
  }
}

bigInt bigIntDivision(bigInt a,bigInt b){
  bigInt c,d;
  bigIntDivisions(a,b,&c,&d);
  return c;
}

bigInt bigIntModular(bigInt a,bigInt b){
  bigInt c,d;
  bigIntDivisions(a,b,&c,&d);
  return d;
}

int bigIntSign(bigInt a){
  int i;
  for(i=BIG_INT_SIZE-1;i>=0;i--) if(a.a[i]){
    if(a.a[i]<0) return -1; else return 1;
  }
  return 0;
}

bigInt bigIntAbs(bigInt a){
  if(bigIntSign(a)==-1) return bigIntMultipleLL(a,-1LL); return a;
}

bigInt bigIntGCD(bigInt a,bigInt b){
  if(bigIntSign(a)==-1) a=bigIntMultipleLL(a,-1);
  if(bigIntSign(b)==-1) b=bigIntMultipleLL(b,-1);
  if(bigIntIsZero(a)) return b;
  return bigIntGCD(bigIntModular(b,a),a);
}

int bigIntToChar(bigInt a,char ret[]){
  int i,j,s=0,len=0; char ct[BIG_INT_CHAR_SIZE]; ll lt;
  if(bigIntSign(a)==-1){
    ret[0]='-'; len=bigIntToChar(bigIntMultipleLL(a,-1LL),ret+1); return len+1;
  }
  rep(i,BIG_INT_SIZE){
    lt=a.a[i]; rep(j,BIG_INT_DIGITS) ct[s++]=lt%10, lt/=10;
  }
  j=0;
  while(s--){
    if(ct[s]) j=1;
    if(j) ret[len++]=ct[s]+'0';
  }
  if(!len) ret[len++]='0';
  ret[len]='\0'; return len;
}

void printBigInt(bigInt a){
  int i,k; char tmp[BIG_INT_CHAR_SIZE];
  k=bigIntToChar(a,tmp); rep(i,k) putchar(tmp[i]);
}

void putBigInt(bigInt a){
  char tmp[BIG_INT_CHAR_SIZE];
  bigIntToChar(a,tmp); puts(tmp);
}

bigInt bigIntDivisionLL(bigInt a,ll b){
  bigInt res; ll tmp;
  bigIntDivisionsLL(a, b, &res, &tmp);
  return res;
}

bigInt bigIntSqrt(bigInt a){
  bigInt c1=bigIntZero(),c2=a,c,mul;

  while( bigIntGreaterThan(c2,c1) ){
    c = bigIntDivisionLL( bigIntPlus(bigIntPlus(c1,c2),bigIntOne()), 2);
    mul = bigIntMultiple(c,c);
    if( bigIntGreaterThan(mul,a) ) c2=bigIntMinus(c,bigIntOne()); else c1=c;
  }

  return c1;
}

bigInt bigIntCubicRoot(bigInt a){
  bigInt c1=bigIntZero(),c2=a,c,mul;

  while( bigIntGreaterThan(c2,c1) ){
    c = bigIntDivisionLL( bigIntPlus(bigIntPlus(c1,c2),bigIntOne()), 2);
    mul = bigIntMultiple(c,bigIntMultiple(c,c));
    if( bigIntGreaterThan(mul,a) ) c2=bigIntMinus(c,bigIntOne()); else c1=c;
  }

  return c1;
}


void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}

template<class T> T GCD(T a,T b){T r; while(a){r=b; b=a; a=r%a;} return b;}
void extended_euclid(ll x,ll y,ll *c,ll *a,ll *b){
  ll a0,a1,a2,b0,b1,b2,r0,r1,r2,q;
  r0=x; r1=y; a0=1; a1=0; b0=0; b1=1;
  while(r1>0){
    q=r0/r1; r2=r0%r1; a2=a0-q*a1; b2=b0-q*b1;
    r0=r1; r1=r2; a0=a1; a1=a2; b0=b1; b1=b2;
  }
  *c=r0; *a=a0; *b=b0;
}

int solve(ll Vx, ll Vy, ll Sx, ll Sy, ll Dx, ll Dy){
  if(Vx < 0) return solve(-Vx, Vy, -Sx, Sy, Dx, Dy);
  if(Vy < 0) return solve(Vx, -Vy, Sx, -Sy, Dx, Dy);

  int i;
  ll VVx, VVy, X, Y, g, A, B, C, D, XX, YY, Bx, By;
  bigInt BBx, BBy, gg, gg1, gg2;

//  printf("V %lld %lld , S %lld %lld, D %lld %lld\n",Vx,Vy,Sx,Sy,Dx,Dy);
  
  g = GCD(Vx, Vy);
  VVx = Vx / g;
  VVy = Vy / g;

  g = Sx / Dx;
  Sx -= g * Dx;
  g = Sy / Dy;
  Sy -= g * Dy;
  while(Sx < 0) Sx += Dx; while(Sx >= Dx) Sx -= Dx;
  while(Sy < 0) Sy += Dy; while(Sy >= Dy) Sy -= Dy;

  A = Dx * VVy;
  B = Dy * VVx;
  C = VVx * Sy - VVy * Sx;

  g = GCD(A,B);
  if(C%g) return 0;
  A /= g; B /= g; C /= g;

//  printf("ABC %lld %lld %lld\n",A,B,C);
  
  extended_euclid(A, B, &D, &X, &Y);
  BBx = bigIntMultiple(llToBigInt(C), llToBigInt(X));
  BBy = bigIntMultiple(llToBigInt(-C), llToBigInt(Y));
//  printf("XY %lld %lld\n",X,Y);
//  printf("XYB %lld %lld\n",Bx,By);

  if(A && B){
    gg1 = bigIntDivision(BBx, llToBigInt(B));
    gg2 = bigIntDivision(BBy, llToBigInt(A));
    if(bigIntGreaterThan(gg1,gg2)) gg = gg2; else gg = gg1;
    BBx = bigIntMinus(BBx, bigIntMultiple(gg, llToBigInt(B)));
    BBy = bigIntMinus(BBy, bigIntMultiple(gg, llToBigInt(A)));

    if(bigIntGreaterThan(BBx, llToBigInt(2000000000000LL))) return 0;
    if(bigIntGreaterThan(BBy, llToBigInt(2000000000000LL))) return 0;

    Bx = By = 0;
    rep(i,BIG_INT_SIZE) Bx = Bx * BIG_INT_BASE + BBx.a[BIG_INT_SIZE-1-i];
    rep(i,BIG_INT_SIZE) By = By * BIG_INT_BASE + BBy.a[BIG_INT_SIZE-1-i];
    
    while(Bx-B >= 0 && By-A >= 0) Bx -= B, By -= A;
    while(Bx < 0 || By < 0) Bx += B, By += A;
  } else {
    Bx = By = 0;
  }

//  printf("XYB %lld %lld\n",Bx,By);

  if((double)Bx * Dx > 2e18) return 0;
  if((double)By * Dy > 2e18) return 0;
  XX = Sx + Bx * Dx;
  YY = Sy + By * Dy;

//  printf("XY %lld %lld\n",XX,YY);

  if(XX <= Vx && YY <= Vy) return 1;
  return 0;
}

int Q;
int W, H, D, HX, HY, MX, MY, VX, VY;

int main(){
  int i, j, k;

  reader(&Q);
  while(Q--){
    reader(&W,&H,&D);
    reader(&MX,&MY);
    reader(&HX,&HY);
    reader(&VX,&VY);

    k = 0;
    if(!k) k |= solve((ll)VX*D, (ll)VY*D, MX-HX, MY-HY, 2*W, 2*H);
    if(!k) k |= solve((ll)VX*D, (ll)VY*D, (2*W-MX)-HX, MY-HY, 2*W, 2*H);
    if(!k) k |= solve((ll)VX*D, (ll)VY*D, MX-HX, (2*H-MY)-HY, 2*W, 2*H);
    if(!k) k |= solve((ll)VX*D, (ll)VY*D, (2*W-MX)-HX, (2*H-MY)-HY, 2*W, 2*H);

    writer(k?"Hit\n":"Miss\n");
  }

  return 0;
}
yukicoder

結果

テストケース

ソースコード
