oj.uz

Submission #9349

# Submission time Handle Problem Language Result Execution time Memory
9349 2014-09-28T05:47:35 Z ainu7 Quaternion inverse (kriii2_Q) C++
4 / 4
 784 ms 1676 KB 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

int mmod;
int inv_mod(int a, int b) {
  if (a < 0) return (mmod - inv_mod(-a, b)) % mmod;
  if (a == 1) return b;
  int div = mmod / a + 1;
  return inv_mod((a * (long long)div) % mmod, (b * (long long)div) % mmod);
}

int A[4][4], B[4];

void solve() {
  for (int i=0; i<4; i++) {
    int idx = -1;
    for (int j=i; j<4; j++)
      if (A[j][i]) idx = j;
    if (idx == -1) continue;
    for (int j=0; j<4; j++)
      swap(A[i][j], A[idx][j]);
    swap(B[i], B[idx]);

    int mm = inv_mod(A[i][i], 1);
    B[i] = (B[i] * (long long)mm) % mmod;
    for (int j=i; j<4; j++)
      A[i][j] = (A[i][j] * (long long)mm) % mmod;

    for (int j=0; j<4; j++) if (i != j) {
      B[j] = (B[j] - A[j][i] * (long long)B[i]) % mmod;
      if (B[j] < 0) B[j] += mmod;
      for (int k=3; k>=i; k--) {
        A[j][k] = (A[j][k] - A[i][k] * (long long)A[j][i]) % mmod;
        if (A[j][k] < 0) A[j][k] += mmod;
      }
    }
  }

  for (int i=0; i<4; i++)
    if (!A[i][i] && B[i]) {
      printf("0 0 0 0\n");
      return;
    }
  printf("%d %d %d %d\n", B[0], B[1], B[2], B[3]);
}

int main()
{
  int T;
  cin >> mmod >> T;

  for (int i=0; i<T; i++) {
    int a1, b1, c1, d1;
    cin >> a1 >> b1 >> c1 >> d1;
    A[0][0] = a1; A[0][1] = -b1; A[0][2] = -c1; A[0][3] = -d1;
    A[1][0] = b1; A[1][1] = a1; A[1][2] = -d1; A[1][3] = c1;
    A[2][0] = c1; A[2][1] = d1; A[2][2] = a1; A[2][3] = -b1;
    A[3][0] = d1; A[3][1] = -c1; A[3][2] = b1; A[3][3] = a1;

    B[0] = 1;
    B[1] = B[2] = B[3] = 0;
    solve();
  }
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1676 KB Output is correct
2 Correct 0 ms 1676 KB Output is correct
3 Correct 8 ms 1676 KB Output is correct
4 Correct 16 ms 1676 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 1676 KB Output is correct
2 Correct 484 ms 1676 KB Output is correct
3 Correct 520 ms 1676 KB Output is correct
4 Correct 576 ms 1676 KB Output is correct
5 Correct 628 ms 1676 KB Output is correct
6 Correct 568 ms 1676 KB Output is correct
7 Correct 608 ms 1676 KB Output is correct
8 Correct 668 ms 1676 KB Output is correct
9 Correct 688 ms 1676 KB Output is correct
10 Correct 664 ms 1676 KB Output is correct
11 Correct 784 ms 1676 KB Output is correct
12 Correct 708 ms 1676 KB Output is correct
13 Correct 768 ms 1676 KB Output is correct
14 Correct 672 ms 1676 KB Output is correct
15 Correct 720 ms 1676 KB Output is correct