Code Submission Evaluation System Login

CSES - HIIT Open 2016

HIIT Open 2016

Contest start:2016-05-28 11:00:00
Contest end:2016-05-28 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics


History
2016-05-28 12:20:05
2016-05-28 12:17:51
2016-05-28 12:16:29
2016-05-28 12:02:51
Task:Judge correctness
Sender:Game of Nolife
Submission time:2016-05-28 12:20:05
Status:READY
Result:ACCEPTED

Show test data

Code

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;

int p = 10;
int n;

int A [5050][5050];
int X [5050][5050];
ll v [5050];
ll vv [5050];
ll vvv [5050];
ll u [5050];

ll parse_char(char c) {
	if (c == '+') {
		return 62;
	} else if (c == '/') {
		return 63;
	} else if (c>='0'&&c<='9') {
		return (c - '0')+52;
	} else if (c>='A'&&c<='Z'){
		return c - 'A';
	}
	return (c - 'a')+26;
}

bool random_test() {
	for (int i = 0; i < n; i++) {
		v[i] = rand()%64;
	}
	for (int i = 0; i < n; i++) {
		vv[i] = 0;
		for (int j = 0; j < n; j++) {
			vv[i] += A[j][i]*v[j];
		}
		vv[i] &= 63;
	}
	for (int i = 0; i < n; i++) {
		vvv[i] = 0;
		for (int j = 0; j < n; j++) {
			vvv[i] += A[i][j]*vv[j];
		}
		vvv[i] &= 63;
	}
	for (int i = 0; i < n; i++) {
		u[i] = 0;
		for (int j = 0; j < n; j++) {
			u[i] += X[j][i]*v[j];
		}
		u[i] &= 63;
	}
	for (int i = 0; i < n; i++) {
		//cout << "u1: " << u[i] << "\n";
		if ((u[i] - vvv[i])%64 != 0) {
			return false;
		}
	}
	return true;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	for (int tc = 0; tc < t; tc++) {
		cin >> n;
		for (int i = 0; i < n + 10; i++) {
			for (int j = 0; j < n + 10; j++) {
				A[i][j] = 0;
				X[i][j] = 0;
			}
		}
		for (int i = 0; i < n; i++) {
			string row;
			cin >> row;
			for (int j = 0; j < n; j++) {
				A[i][j] = parse_char(row[j]);
				//cout << A[i][j] << " ";
			}
			//cout << "\n";
		}
		for (int i = 0; i < n; i++) {
			string row;
			cin >> row;
			for (int j = 0; j < n; j++) {
				X[i][j] = parse_char(row[j]);
				//cout << X[i][j] << " ";
			}
			//cout << "\n";
		}
		bool ok = true;
		for (int i = 0; i < p; i++) {
			ok = ok&&random_test();
			if (!ok) {
				break;
			}
		}
		if (ok) {
			cout << "1\n";
		} else {
			cout << "0\n";
		}
	}
}