oj.uz

Submission #9793

# Submission time Handle Problem Language Result Execution time Memory
9793 2014-09-28T08:58:14 Z jaehadad Quaternion inverse (kriii2_Q) C++14
4 / 4
 944 ms 1680 KB 
#include<cstdio>
#include<cassert>
#include<cstring>
#include<map>
#include<set>
#include<time.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<utility>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

int M;

long pow(long long a, long long n, long long M) {
  long long ret = 1, unit = a % M;
  for(int y = 0; (1ll<<y) <= n; ++y) {
    if(n & (1ll << y)) 
      ret = (ret * unit) % M;
    unit = (unit * unit) % M;
  }
  return ret;
}

long long mod_inverse(long long a, long long M) {
  return pow(a, M-2, M);
}

vector<int> eliminate(vector<vector<int> >& A, vector<int>& b) {
  int n = A.size();
  for(int y = 0; y < n; ++y) {
    for(int y2 = y; y2 < n; ++y2) {
      if(A[y2][y]) {
        if(y != y2) {
          swap(A[y], A[y2]);
          swap(b[y], b[y2]);
        }
        break;
      }
    }
    if(A[y][y] == 0) return vector<int>();

    long long div = mod_inverse(A[y][y], M);
    for(int x = y; x < n; ++x)
      A[y][x] = (A[y][x] * div) % M;
    b[y] = (b[y] * div) % M;

    for(int y2 = y+1; y2 < n; ++y2) {
      long long mult = A[y2][y];
      for(int x = y; x < n; ++x)
        A[y2][x] = (A[y2][x] - (A[y][x] * mult) % M + M) % M;
      b[y2] = (b[y2] - (b[y] * mult) % M + M) % M;
    }
  }

  for(int y = n-1; y >= 0; --y) {
    for(int y2 = y-1; y2 >= 0; --y2) {
      long long mult = A[y2][y];
      for(int x = y; x < n; ++x) 
        A[y2][x] = (A[y2][x] - (A[y][x] * mult) % M + M) % M;
      b[y2] = (b[y2] - (b[y] * mult) % M + M) % M;
    }
  }

  return b;
}

int main() {
  int t;
  cin >> M >> t;
  for(int cc = 0; cc < t; ++cc) {
    vector<vector<int> > A;
    {
      int a, b, c, d;
      cin >> a >> b >> c >> d;
      A.push_back(vector<int>{a, -b, -c, -d});
      A.push_back(vector<int>{b, a, -d, c});
      A.push_back(vector<int>{c, d, a, -b});
      A.push_back(vector<int>{d, -c, b, a});
    }
    vector<int> b = { 1, 0, 0, 0 };
    // for(int i = 0; i < 4; ++i) {
    //   for(int j = 0; j < 4; ++j) {
    //     printf("%d ", A[i][j]);
    //   }
    //   printf("\n");
    // }
    vector<int> sol = eliminate(A, b);
    if(sol.empty())
      printf("0 0 0 0\n");
    else
      printf("%d %d %d %d\n", sol[0], sol[1], sol[2], sol[3]);
  }

}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1680 KB Output is correct
2 Correct 0 ms 1680 KB Output is correct
3 Correct 4 ms 1680 KB Output is correct
4 Correct 12 ms 1680 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB
2 Correct 652 ms 1680 KB Output is correct
3 Correct 704 ms 1680 KB Output is correct
4 Correct 728 ms 1680 KB Output is correct
5 Correct 816 ms 1680 KB Output is correct
6 Correct 700 ms 1680 KB Output is correct
7 Correct 804 ms 1680 KB Output is correct
8 Correct 932 ms 1680 KB Output is correct
9 Correct 880 ms 1680 KB Output is correct
10 Correct 860 ms 1680 KB Output is correct
11 Correct 920 ms 1680 KB Output is correct
12 Correct 884 ms 1680 KB Output is correct
13 Correct 928 ms 1680 KB Output is correct
14 Correct 944 ms 1680 KB Output is correct
15 Correct 904 ms 1680 KB Output is correct