oj.uz

Submission #374975

# Submission time Handle Problem Language Result Execution time Memory
374975 2021-03-08T17:34:18 Z _martynas Cards (LMIO19_korteles) C++11
100 / 100
 88 ms 6744 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MAX_N = 26*26*26*26 + 5;

int n;

char C[MAX_N][4]; // cards
int cnt[MAX_N];
int L[676], R[676], U[676], D[676];

void Read(char IN[])
{
    scanf(" %c%c %c%c", &IN[0], &IN[1], &IN[2], &IN[3]);
}

int Hash2(char a, char b)
{
    return 26 * (a - 'A') + (b - 'A');
}

int Hash4(char Arr[4])
{
    int h = 0;
    for(int i = 0; i < 4; i++)
    {
        h *= 26;
        h += Arr[i] - 'A';
    }
    return h;
}

int Hash4(int a, int b, int c, int d)
{
    int h = a;
    h *= 26;
    h += b;
    h *= 26;
    h += c;
    h *= 26;
    h += d;
    return h;
}

int main()
{
    scanf("%d", &n);

    ll ans = 0;

    for(int i = 0; i < n; i++)
    {
        Read(C[i]);
        L[Hash2(C[i][0], C[i][2])]++;
        R[Hash2(C[i][1], C[i][3])]++;
        U[Hash2(C[i][0], C[i][1])]++;
        D[Hash2(C[i][2], C[i][3])]++;
        cnt[Hash4(C[i])]++;
        //cout << C[i] << endl;
        if(C[i][0] == C[i][2] && C[i][1] == C[i][3]) // counts himself
        {
            ans--;
        }
        if(C[i][0] == C[i][1] && C[i][2] == C[i][3]) // counts himself
        {
            ans--;
        }
    }

    for(int i = 0; i <= 676; i++)
    {
        ans += (ll)L[i] * R[i];
        ans += (ll)U[i] * D[i];
    }

    for(int i = 0; i < 26; i++) for(int j = 0; j < 26; j++)
    {
        for(int k = 0; k < 26; k++) for(int l = 0; l < 26; l++)
        {
            int h1, h2;
            h1 = Hash4(i, j, k, l);
            h2 = Hash4(k, l, i, j);

            /*
            IJ KL
            KL IJ
            */

            if(h1 < h2)
                ans -= cnt[h1] * cnt[h2];

            h2 = Hash4(j, i, l, k);

            /*
            IJ JI
            KL LK
            */

            if(h1 < h2)
                ans -= cnt[h1] * cnt[h2];

            h1 = Hash4(i, j, k, i), h2 = Hash4(j, l, i, j);

            /*
            IJ JL
            KI IJ
            */

            if(h1 != h2)
                ans -= cnt[h1] * cnt[h2];

            h1 = Hash4(k, i, i, j), h2 = Hash4(i, j, j, l);

            /*
            KI IJ
            IJ JL
            */

            if(h1 != h2)
                ans -= cnt[h1] * cnt[h2];

        }
        /*
        IJ JI
        JI IJ
        */
        if(i < j)
        {
            ans += 3 * cnt[Hash4(i, j, j, i)] * cnt[Hash4(j, i, i, j)];
        }
    }

    cout << ans << endl;

    return 0;
}
/* INPUT
3
IO
OI
AA
AA
OI
IO
*/

Compilation message

korteles.cpp: In function 'void Read(char*)':
korteles.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |     scanf(" %c%c %c%c", &IN[0], &IN[1], &IN[2], &IN[3]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
korteles.cpp: In function 'int main()':
korteles.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
korteles.cpp:75:23: warning: iteration 676 invokes undefined behavior [-Waggressive-loop-optimizations]
   75 |         ans += (ll)L[i] * R[i];
      |                    ~~~^
korteles.cpp:73:22: note: within this loop
   73 |     for(int i = 0; i <= 676; i++)
      |                    ~~^~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 4 ms 1644 KB Output is correct
7 Correct 3 ms 620 KB Output is correct
8 Correct 4 ms 2156 KB Output is correct
9 Correct 8 ms 1516 KB Output is correct
10 Correct 3 ms 1900 KB Output is correct
11 Correct 3 ms 364 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 3948 KB Output is correct
2 Correct 82 ms 6632 KB Output is correct
3 Correct 88 ms 6636 KB Output is correct
4 Correct 86 ms 6744 KB Output is correct
5 Correct 83 ms 6636 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 364 KB Output is correct
2 Correct 12 ms 2284 KB Output is correct
3 Correct 56 ms 5124 KB Output is correct
4 Correct 37 ms 3820 KB Output is correct
5 Correct 34 ms 3820 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 364 KB Output is correct
2 Correct 4 ms 1644 KB Output is correct
3 Correct 3 ms 620 KB Output is correct
4 Correct 4 ms 2156 KB Output is correct
5 Correct 8 ms 1516 KB Output is correct
6 Correct 3 ms 1900 KB Output is correct
7 Correct 3 ms 364 KB Output is correct
8 Correct 3 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 3 ms 492 KB Output is correct
11 Correct 3 ms 492 KB Output is correct
12 Correct 82 ms 3948 KB Output is correct
13 Correct 82 ms 6632 KB Output is correct
14 Correct 88 ms 6636 KB Output is correct
15 Correct 86 ms 6744 KB Output is correct
16 Correct 83 ms 6636 KB Output is correct
17 Correct 12 ms 2284 KB Output is correct
18 Correct 56 ms 5124 KB Output is correct
19 Correct 37 ms 3820 KB Output is correct
20 Correct 34 ms 3820 KB Output is correct
21 Correct 23 ms 3052 KB Output is correct
22 Correct 63 ms 5612 KB Output is correct
23 Correct 44 ms 4332 KB Output is correct
24 Correct 44 ms 4332 KB Output is correct