oj.uz

Submission #719727

# Submission time Handle Problem Language Result Execution time Memory
719727 2023-04-06T14:30:45 Z pashka Cards (LMIO19_korteles) C++14
100 / 100
 456 ms 252116 KB 
#include <bits/stdc++.h>

#define long long long int
#define DEBUG
using namespace std;

// @author: pashka

const int M = 10000000;

struct hashmap {
    long keys[M];
    int vals[M];

    void clear() {
        for (int i = 0; i < M; i++) vals[i] = 0;
    }

    int hash(long x) {
        return (x * 239) % M;
    }

    int get(long x) {
        int i = hash(x);
        while (vals[i] != 0) {
            if (keys[i] == x) return vals[i];
            i++;
            if (i == M) i = 0;
        }
        return 0;
    }

    void inc(long x) {
        int i = hash(x);
        while (vals[i] != 0) {
            if (keys[i] == x) {
                vals[i]++;
                return;
            }
            i++;
            if (i == M) i = 0;
        }
        keys[i] = x;
        vals[i] = 1;
    }

};

hashmap m1, m2;

long calc(vector<string> &a, vector<pair<int, int>> p) {
    m1.clear();
    m2.clear();
    long res = 0;
    for (int i = 0; i < (int) a.size(); i++) {
        long s1 = 0, s2 = 0;
        for (auto [x, y]: p) {
            s1 *= 30;
            s2 *= 30;
            s1 += a[i][x] - 'A';
            s2 += a[i][y] - 'A';
        }
        res += m2.get(s1);
        res += m1.get(s2);
        m1.inc(s1);
        m2.inc(s2);
    }
    cerr << res << "\n";
    return res;
}

char buf[10];

int main() {
    ios::sync_with_stdio(false);

    int n;
    scanf("%d", &n);
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        string x, y;
        scanf("%s", buf);
        x = buf;
        scanf("%s", buf);
        y = buf;
        a[i] = x + y;
    }
    long res = 0;
    res += calc(a, {{0, 2},
                    {1, 3}});
    res += calc(a, {{0, 1},
                    {2, 3}});
    res -= calc(a, {{0, 2},
                    {1, 3},
                    {2, 0},
                    {3, 1}}) / 2;
    res -= calc(a, {{0, 1},
                    {2, 3},
                    {1, 0},
                    {3, 2}}) / 2;

    res -= calc(a, {{0, 2},
                    {1, 3},
                    {1, 0},
                    {3, 2}});
    res -= calc(a, {{0, 2},
                    {1, 3},
                    {0, 1},
                    {2, 3}});

    vector<string> a3;
    for (string s: a) {
        if (s[0] == s[3] && s[1] == s[2]) a3.push_back(s);
    }
    res += calc(a3, {{0, 2},
                     {1, 3}}) / 2 * 3;
    cout << res << "\n";


    return 0;
}

Compilation message

korteles.cpp: In function 'long long int calc(std::vector<std::__cxx11::basic_string<char> >&, std::vector<std::pair<int, int> >)':
korteles.cpp:57:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |         for (auto [x, y]: p) {
      |                   ^
korteles.cpp: In function 'int main()':
korteles.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
korteles.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         scanf("%s", buf);
      |         ~~~~~^~~~~~~~~~~
korteles.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         scanf("%s", buf);
      |         ~~~~~^~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 78640 KB Output is correct
2 Correct 83 ms 78872 KB Output is correct
3 Correct 84 ms 79640 KB Output is correct
4 Correct 84 ms 79820 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 78640 KB Output is correct
2 Correct 83 ms 78872 KB Output is correct
3 Correct 84 ms 79640 KB Output is correct
4 Correct 84 ms 79820 KB Output is correct
5 Correct 78 ms 78664 KB Output is correct
6 Correct 98 ms 98696 KB Output is correct
7 Correct 85 ms 92028 KB Output is correct
8 Correct 105 ms 140396 KB Output is correct
9 Correct 96 ms 117448 KB Output is correct
10 Correct 99 ms 115524 KB Output is correct
11 Correct 85 ms 78620 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 249452 KB Output is correct
2 Correct 456 ms 252116 KB Output is correct
3 Correct 451 ms 252080 KB Output is correct
4 Correct 432 ms 252032 KB Output is correct
5 Correct 452 ms 252064 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 78620 KB Output is correct
2 Correct 164 ms 235920 KB Output is correct
3 Correct 355 ms 244484 KB Output is correct
4 Correct 270 ms 240584 KB Output is correct
5 Correct 268 ms 240684 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 78664 KB Output is correct
2 Correct 98 ms 98696 KB Output is correct
3 Correct 85 ms 92028 KB Output is correct
4 Correct 105 ms 140396 KB Output is correct
5 Correct 96 ms 117448 KB Output is correct
6 Correct 99 ms 115524 KB Output is correct
7 Correct 85 ms 78620 KB Output is correct
8 Correct 80 ms 78640 KB Output is correct
9 Correct 83 ms 78872 KB Output is correct
10 Correct 84 ms 79640 KB Output is correct
11 Correct 84 ms 79820 KB Output is correct
12 Correct 436 ms 249452 KB Output is correct
13 Correct 456 ms 252116 KB Output is correct
14 Correct 451 ms 252080 KB Output is correct
15 Correct 432 ms 252032 KB Output is correct
16 Correct 452 ms 252064 KB Output is correct
17 Correct 164 ms 235920 KB Output is correct
18 Correct 355 ms 244484 KB Output is correct
19 Correct 270 ms 240584 KB Output is correct
20 Correct 268 ms 240684 KB Output is correct
21 Correct 200 ms 238824 KB Output is correct
22 Correct 370 ms 248172 KB Output is correct
23 Correct 293 ms 243504 KB Output is correct
24 Correct 293 ms 243672 KB Output is correct