oj.uz

Submission #9328

# Submission time Handle Problem Language Result Execution time Memory
9328 2014-09-28T05:36:47 Z myungwoo Quaternion inverse (kriii2_Q) C++14
1 / 4
 236 ms 1476 KB 
#include <stdio.h>
#include <algorithm>
using namespace std;

#define MAXM 100005
typedef long long lld;

int M, T;
int A, B, C, D;
int inv[MAXM];

int get_inv(int n)
{
	int m = M-2, ret = 1, v = n;
	for (;m;m>>=1, v=(lld)v*v%M) if (m&1) ret = (lld)ret*v%M;
	return ret;
}

int main()
{
	int i, j, k;
	scanf("%d%d", &M, &T);
	for (i=1;i<M;i++) inv[i] = get_inv(i);
	while (T--){
		scanf("%d%d%d%d", &A, &B, &C, &D);
		int p[4][5] ={
				{A, -B, -C, -D, 1},
				{B, A, -D, C, 0},
				{C, D, A, -B, 0},
				{D, -C, B, A, 0}
		};
		for (i=0;i<4;i++) for (j=0;j<5;j++) p[i][j] = (p[i][j]+M)%M;
		for (i=0;i<4;i++){
			if (!p[i][i]){
				for (j=i;j<4;j++) if (p[j][i]) break;
				if (j == 4) break;
				for (k=0;k<5;k++) swap(p[i][k], p[j][k]);
			}
			int v = inv[p[i][i]];
			for (j=0;j<5;j++) p[i][j] = (lld)p[i][j]*v%M;
			for (j=0;j<4;j++) if (i != j){
				int r = p[j][i];
				for (k=0;k<5;k++){
					p[j][k] = (p[j][k]-p[i][k]*r%M+M)%M;
				}
			}
		}
		if (i < 4) puts("0 0 0 0"); // no answer
		else{
			int ans[4]={0, };
			for (i=0;i<4;i++) printf("%d ", p[i][4]);
			puts("");
		}
	}
}

Subtask #1
1.0 / 1.0

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

Subtask #2
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 1476 KB Output is correct
2 Correct 188 ms 1476 KB Output is correct
3 Correct 196 ms 1476 KB Output is correct
4 Correct 208 ms 1476 KB Output is correct
5 Correct 204 ms 1476 KB Output is correct
6 Correct 204 ms 1476 KB Output is correct
7 Correct 204 ms 1476 KB Output is correct
8 Correct 216 ms 1476 KB Output is correct
9 Correct 232 ms 1476 KB Output is correct
10 Incorrect 236 ms 1476 KB Output isn't correct
11 Halted 0 ms 0 KB -