CSES - HIIT Open 2016 - Results
Submission details
Task:Judge correctness
Sender:Ace of Spades
Submission time:2016-05-28 15:36:38 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1--details
#20.57 sdetails
#32.12 sdetails
#4ACCEPTED1.31 sdetails
#52.59 sdetails
#62.59 sdetails
#7ACCEPTED1.32 sdetails
#8ACCEPTED1.30 sdetails
#9ACCEPTED1.30 sdetails
#102.60 sdetails

Code

#include<bits/stdc++.h>


using namespace std;
const int MN = 5555;
const int MOD = 64;
const int N = 13;
short a[MN][MN];
short x[MN][MN];
short sumA[4*N][MN];
short sumX[4*N][MN];
bool lol[MN]; 

int main(void) {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    int tt;
    cin>>tt;
    for(int xx = 0; xx < tt; ++xx) {
        memset(a, 0, sizeof a);
        memset(x, 0, sizeof x);
        memset(sumA, 0, sizeof sumA);
        memset(sumX, 0, sizeof sumX);
        int n;
        cin>>n;
        for(int i = 0; i < n; ++i ) {
            for(int j = 0; j < n; ++j) {
                char q = 0;
                cin>>q;
                if(q >= 'A' && q <= 'Z') {
                    a[i][j] = q - 'A';
                }
                if(q >= 'a' && q <= 'z') {
                    a[i][j] = q - 'a'+26;
                }
                if(q >= '0' && q <= '9') {
                    a[i][j] = q-'0'+52;
                }
                if(q == '+') a[i][j] = 62;
                if(q == '/') a[i][j] = 63;
            //    cout<<a[i][j]<<' ';
            }
        //cout<<'\n';
        }
        //cout<<'\n';
        for(int i = 0; i < n; ++i ) {
            for(int j = 0; j < n; ++j) {
                char q = 0;
                cin>>q;
                if(q >= 'A' && q <= 'Z') {
                    x[i][j] = q - 'A';
                }
                if(q >= 'a' && q <= 'z') {
                    x[i][j] = q - 'a'+26;
                }
                if(q >= '0' && q <= '9') {
                    x[i][j] = q-'0'+52;
                }
                if(q == '+') x[i][j] = 62;
                if(q == '/') x[i][j] = 63;
         //   cout<<x[i][j]<<' ';
            }
        //cout<<'\n';
        }
        //cout<<'\n';
        int q = 1;
        for(int i = 0; i*2 < 3*N; ++i, q *= 2) {
            /*
            for(int k = 0; k < n; ++k) {
                    if((k>>i)%2 == 0) { 
                        cout<<k<<' ';
                     }
                    cout<<'\n';
            }
            continue;
            */
            if(i < N) {

                for(int j = 0; j < n; ++j) {
                    for(int k = 0; k < n; ++k) {
                        if((k>>i)%2 == 0) {
                            sumA[i][j] += a[k][j];
                            sumX[i][j] += x[k][j];
                            //          cout<<k<<' ';
                        }
                    }
                    //   cout<<'\n';
                    sumX[i][j] %= MOD;
                    sumA[i][j] %= MOD;
                    //cout<<sumX[i][j]<<' '<<sumA[i][j]<<' '<<"asdfa\n";
                }
            }
            else {
                for(int j = 0; j < n; ++j) {
                    lol[j] = rand()%2;
                }
                for(int j = 0; j < n; ++j) {
                    for(int k = 0; k < n; ++k) {
                        if(lol[k]) {
                            sumA[i][j] += a[k][j];
                            sumX[i][j] += x[k][j];
                        }
                    }
                    //   cout<<'\n';
                    sumX[i][j] %= MOD;
                    sumA[i][j] %= MOD;
                    //cout<<sumX[i][j]<<' '<<sumA[i][j]<<' '<<"asdfa\n";
                }
            }
            //cout<<'\n';
            for(int j = 0; j < n; ++j) {
                int q = 0;
                int w = sumX[i][j];
                for(int k = 0; k < n; ++k) {
                    q += sumA[i][k] * a[j][k];
                }
                q %= MOD;
                w %= MOD;
               // cout<<q<<' '<<w<<'\n';
                if(q != w) {
                    goto ohi;
                }
            }
        }
        cout<<1<<'\n';
        continue;
ohi:;
    cout<<0<<'\n';

    }


    return 0;
}

Test details

Test 1

Verdict:

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

correct output
0
0
1
1
1
...

user output
(empty)

Test 2

Verdict:

input
3
666
OvHf9jpB0RViia/ZD3gRQ7o1FELYh3...

correct output
0
0
1

user output
0
0
0

Test 3

Verdict:

input
2
517
RWVknnH+hL6AfeKFbOu6OuAJL9dvLw...

correct output
0
1

user output
0
0

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
0

Test 6

Verdict:

input
1
5000
b0V0j4vQ8CeiJrcUk2yssPF1B9EEDb...

correct output
1

user output
0

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
0