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 15:59:52
2016-05-28 15:57:07
2016-05-28 15:56:35
2016-05-28 15:55:48
2016-05-28 15:54:36
2016-05-28 15:36:38
2016-05-28 15:35:23
2016-05-28 15:34:29
2016-05-28 15:21:25
Task:Judge correctness
Sender:Ace of Spades
Submission time:2016-05-28 15:59:52
Status:READY
Result:WRONG ANSWER

Show test data

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[3*N][MN];
short sumX[3*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) {
                a[i][j] = 0;
                x[i][j] = 0;
            }
        }
        for(int i = 0; i < 3*N; ++i) {
            for(int j = 0; j < n; ++j) {
                sumA[i][j] = 0;
                sumX[i][j] = 0;
            }
        }
        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 < 6*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 k = 0; k < n; ++k) {
                    if((k>>i)%2 == 0) {
                    for(int j = 0; j < n; ++j) {
                            sumA[0][j] += a[k][j];
                            sumX[0][j] += x[k][j];
                            //          cout<<k<<' ';
                        }
                    }
                    //   cout<<'\n';
                    //cout<<sumX[i][j]<<' '<<sumA[i][j]<<' '<<"asdfa\n";
                }
                for(int j = 0; j < n; ++j) {
                    sumA[0][j] %= MOD;
                    sumX[0][j] %= MOD;
                }
            }
            else {
                for(int j = 0; j < n; ++j) {
                    lol[j] = rand()%2;
                }
                    for(int k = 0; k < n; ++k) {
                        if(lol[k]) {
                for(int j = 0; j < n; ++j) {
                            sumA[0][j] += a[k][j];
                            sumX[0][j] += x[k][j];
                        }
                    }
                    //   cout<<'\n';
                    //cout<<sumX[i][j]<<' '<<sumA[i][j]<<' '<<"asdfa\n";
                }
                for(int j = 0; j < n; ++j) {
                    sumA[0][j] %= MOD;
                    sumX[0][j] %= MOD;
                }
            }
            //cout<<'\n';
            for(int j = 0; j < n; ++j) {
                int q = 0;
                int w = sumX[0][j];
                for(int k = 0; k < n; ++k) {
                    q += sumA[0][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;
}