CSES - HIIT Open 2016 - Results
Submission details
Task:Judge correctness
Sender:Game of Nolife
Submission time:2016-05-28 12:16:29 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.08 sdetails
#2--details
#3--details
#4ACCEPTED0.93 sdetails
#5--details
#6--details
#7ACCEPTED0.93 sdetails
#8ACCEPTED0.93 sdetails
#9ACCEPTED0.94 sdetails
#10--details

Code

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

int p = 100;
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] %= 64;
		}
	}
	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] %= 64;
		}
	}
	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] %= 64;
		}
	}
	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";
		}
	}
}

Test details

Test 1

Verdict: ACCEPTED

input
500
12
N49lyQuAZh1l
PwNJA+wuTBr+
HO09lJg8kbup
...

correct output
0
0
1
1
1
...

user output
0
0
1
1
1
...

Test 2

Verdict:

input
3
666
OvHf9jpB0RViia/ZD3gRQ7o1FELYh3...

correct output
0
0
1

user output
(empty)

Test 3

Verdict:

input
2
517
RWVknnH+hL6AfeKFbOu6OuAJL9dvLw...

correct output
0
1

user output
(empty)

Test 4

Verdict: ACCEPTED

input
1
5000
QP9pS1MOq6eDDKGQh//TrJUIvbM53a...

correct output
0

user output
0

Test 5

Verdict:

input
1
5000
RSX7ZuQE6A94s8s+9oP1uCDHRkmZ+7...

correct output
1

user output
(empty)

Test 6

Verdict:

input
1
5000
b0V0j4vQ8CeiJrcUk2yssPF1B9EEDb...

correct output
1

user output
(empty)

Test 7

Verdict: ACCEPTED

input
1
5000
VLdpW71f4Cdr+xdCRlwmAnNfMjqwMU...

correct output
0

user output
0

Test 8

Verdict: ACCEPTED

input
1
5000
kBZaGETPWmyNR4NCvCPbJnvq2+JBfP...

correct output
0

user output
0

Test 9

Verdict: ACCEPTED

input
1
5000
PES9AhJn+FZBVO5gqRLYbavSvaDUfU...

correct output
0

user output
0

Test 10

Verdict:

input
1
5000
EoXwgdrAtKtV4M7jn0jAkNwkJX+be9...

correct output
1

user output
(empty)