oj.uz

Submission #9799

# Submission time Handle Problem Language Result Execution time Memory
9799 2014-09-28T08:59:44 Z jaehadad Quaternion inverse (kriii2_Q) C++14
4 / 4
 948 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;

long long M;

long pow(long long a, long long n, long long M) {
  long long ret = 1, unit = a % M;
  for(long long 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<long long> eliminate(vector<vector<long long> >& A, vector<long long>& b) {
  long long n = A.size();
  for(long long y = 0; y < n; ++y) {
    for(long long 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<long long>();

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

    for(long long y2 = y+1; y2 < n; ++y2) {
      long long mult = A[y2][y];
      for(long long 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(long long y = n-1; y >= 0; --y) {
    for(long long y2 = y-1; y2 >= 0; --y2) {
      long long mult = A[y2][y];
      for(long long 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() {
  long long t;
  cin >> M >> t;
  for(long long cc = 0; cc < t; ++cc) {
    vector<vector<long long> > A;
    {
      long long a, b, c, d;
      cin >> a >> b >> c >> d;
      A.push_back(vector<long long>{a, -b, -c, -d});
      A.push_back(vector<long long>{b, a, -d, c});
      A.push_back(vector<long long>{c, d, a, -b});
      A.push_back(vector<long long>{d, -c, b, a});
    }
    vector<long long> b = { 1, 0, 0, 0 };
    // for(long long i = 0; i < 4; ++i) {
    //   for(long long j = 0; j < 4; ++j) {
    //     printf("%d ", A[i][j]);
    //   }
    //   printf("\n");
    // }
    vector<long long> 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 0 ms 1680 KB Output is correct
4 Correct 8 ms 1680 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 1680 KB Output is correct
2 Correct 736 ms 1680 KB Output is correct
3 Correct 736 ms 1680 KB Output is correct
4 Correct 796 ms 1680 KB Output is correct
5 Correct 752 ms 1680 KB Output is correct
6 Correct 752 ms 1680 KB Output is correct
7 Correct 804 ms 1680 KB Output is correct
8 Correct 856 ms 1680 KB Output is correct
9 Correct 836 ms 1680 KB Output is correct
10 Correct 892 ms 1680 KB Output is correct
11 Correct 948 ms 1680 KB Output is correct
12 Correct 908 ms 1680 KB Output is correct
13 Correct 884 ms 1680 KB Output is correct
14 Correct 928 ms 1680 KB Output is correct
15 Correct 852 ms 1680 KB Output is correct