CSES - HIIT Open 2016 - Results
Submission details
Task:Judge correctness
Sender:Barely Div 1
Submission time:2016-05-28 14:35:59 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.06 sdetails
#2ACCEPTED1.32 sdetails
#32.16 sdetails
#42.62 sdetails
#52.63 sdetails
#62.63 sdetails
#72.62 sdetails
#82.94 sdetails
#92.53 sdetails
#102.62 sdetails

Code


#include <vector>
#include <iostream>
#include <string>



using namespace std;

int getnum(char c) {
	if (c >= 'A' && c <= 'Z') return c - 'A';
	if (c >= 'a' && c <= 'z') return c - 'a' + 26;
	if (c >= '0' && c <= '9') return c - '0' + 52;
	if (c == '+') return 62;
	return 63;
}





//test(m, m_t, ans, r);

bool test(vector<vector<int>> & m, vector<vector<int>> & m_t, vector<vector<int>> & ans, vector<int> & r) {
	int n = m.size();
	vector<long long> check1(n);
	vector<long long> check2(n);
	for (int row = 0; row < n; row++) {
		for (int col = 0; col < n; col++) {
			check1[row] += r[col]*m_t[row][col];
		}
		check1[row] %= 64;
	}

//	for(auto x : check1) cout << "asd " << x << endl;
/*
cout << endl;
for (auto v : m) { for (auto a : v) cout << (int)a << " "; cout << endl; }
cout << endl;
for (auto v : m_t) { for (auto a : v) cout << (int)a << " "; cout << endl; }
cout << endl;
for (auto v : ans) { for (auto a : v) cout << (int)a << " "; cout << endl; }
cout << endl;
*/
//for (auto a : r) cout << a << " "; cout << endl;
//for (auto a : check1) cout << a << " "; cout << endl;
//for (auto a : check1) cout << a << " "; cout << endl;
	vector<long long> tmpr = check1;
	for (int row = 0; row < n; row++) {
		check1[row] = 0;
		for (int col = 0; col < n; col++) {
			check1[row] += tmpr[col]*m[row][col];
		}
		check1[row] %= 64;
	}

	for (int row = 0; row < n; row++) {
		for (int col = 0; col < n; col++) {
			check2[row] += r[col]*ans[row][col];
		}
		check2[row] %= 64;
	}
//cout << endl;
//for (auto a : check1) cout << a << " "; cout << endl;
//for (auto a : check2) cout << a << " "; cout << endl;
//cout << check1.size() << " " << check2.size() << endl;
//cout << endl;
	return check1 == check2;

}



int main() {
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		vector<vector<int>> m(n);
		vector<vector<int>> ans(n);
		int ntmp = n;
		int idx = 0;
		while (ntmp--) {
			string s; cin >> s;
			for (auto c : s) {
				m[idx].push_back(getnum(c));
			}
			idx++;
		}
		
		ntmp = n;
		idx = 0;
		while (ntmp--) {
			string s; cin >> s;
			for (auto c : s) {
				ans[idx].push_back(getnum(c));
			}
			idx++;
		}
		
//cout << "QWE" << endl;
		vector<vector<int>> m_t(n, vector<int>(n));
		for (int row = 0; row < n; row++) {
			for (int col = 0; col < n; col++) {
//cout << row << " " << col << endl;
//cout << m_t.size() << " " << m_t[0].size() << endl;
//cout << m.size() << " " << m[0].size() << endl;
				m_t[col][row] = m[row][col];
//cout << "asd" << endl;
			}
		}
		bool printed = false;
		for (int testn = 0; testn < 10; testn++) {
			vector<int> r(n);
			for (int i = 0; i < n; i++) {
				r[i] = rand() % 64;
			}
			if (!test(m, m_t, ans, r)) {
				cout << "0" << "\n";
				printed = true;
				break;
			}
		}
		if (!printed) cout << "1" << "\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: ACCEPTED

input
3
666
OvHf9jpB0RViia/ZD3gRQ7o1FELYh3...

correct output
0
0
1

user output
0
0
1

Test 3

Verdict:

input
2
517
RWVknnH+hL6AfeKFbOu6OuAJL9dvLw...

correct output
0
1

user output
0

Test 4

Verdict:

input
1
5000
QP9pS1MOq6eDDKGQh//TrJUIvbM53a...

correct output
0

user output
(empty)

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:

input
1
5000
VLdpW71f4Cdr+xdCRlwmAnNfMjqwMU...

correct output
0

user output
(empty)

Test 8

Verdict:

input
1
5000
kBZaGETPWmyNR4NCvCPbJnvq2+JBfP...

correct output
0

user output
(empty)

Test 9

Verdict:

input
1
5000
PES9AhJn+FZBVO5gqRLYbavSvaDUfU...

correct output
0

user output
(empty)

Test 10

Verdict:

input
1
5000
EoXwgdrAtKtV4M7jn0jAkNwkJX+be9...

correct output
1

user output
(empty)