oj.uz

Submission #9777

# Submission time Handle Problem Language Result Execution time Memory
9777 2014-09-28T08:53:07 Z jaehadad Quaternion inverse (kriii2_Q) C++14
1 / 4
 1000 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 = 0; 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 = 0; 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 = 0; 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 0 ms 1680 KB Output is correct
4 Correct 16 ms 1680 KB Output is correct

Subtask #2
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 1680 KB Output is correct
2 Correct 760 ms 1680 KB Output is correct
3 Correct 828 ms 1680 KB Output is correct
4 Correct 792 ms 1680 KB Output is correct
5 Correct 792 ms 1680 KB Output is correct
6 Correct 808 ms 1680 KB Output is correct
7 Correct 868 ms 1680 KB Output is correct
8 Correct 944 ms 1680 KB Output is correct
9 Correct 924 ms 1680 KB Output is correct
10 Correct 980 ms 1680 KB Output is correct
11 Correct 916 ms 1680 KB Output is correct
12 Correct 892 ms 1680 KB Output is correct
13 Correct 936 ms 1680 KB Output is correct
14 Execution timed out 1000 ms 1680 KB Program timed out
15 Halted 0 ms 0 KB -