oj.uz

Submission #872990

# Submission time Handle Problem Language Result Execution time Memory
872990 2023-11-14T08:49:25 Z tsumondai Set (COCI21_set) C++14
110 / 110
 124 ms 27732 KB 
/*
Cho một số lượng các lá bài được biểu diễn bằng giá trị 1 2 3, một bộ ba unorder tripet là một cặp mà trong đó
các phần tử ở vị trí tương ứng đều bằng nhau hoặc khác nhau đôi một.
*/


#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e6 + 5;
 
const int oo = 1e18, mod = 1e9 + 7;

int n, k;
int cnt[N];

struct Z_adjoin_w {
    int x, y;

    Z_adjoin_w () {
        x = y = 0;
    }

    Z_adjoin_w (int _x, int _y) {
        x = _x; y = _y;
    }
} P[N];

const Z_adjoin_w w = Z_adjoin_w(0, 1);
const Z_adjoin_w w2 = Z_adjoin_w(-1, -1);

Z_adjoin_w add (Z_adjoin_w a, Z_adjoin_w b) {
    return Z_adjoin_w(a.x + b.x, a.y + b.y);
}

Z_adjoin_w div_by_3 (Z_adjoin_w a) {
    return Z_adjoin_w(a.x / 3, a.y / 3);
}

Z_adjoin_w mul (Z_adjoin_w a, Z_adjoin_w b) {
    return Z_adjoin_w(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x - a.y * b.y);
}

void modified_FWHT (bool invert) {
    int siz = 1;
    for (int i = 0; i < k; i++) siz *= 3;

    for (int len = 1; len < siz; len *= 3) {
        for (int i = 0; i < siz; i += 3 * len) {
            for (int j = 0; j < len; j++) {
                Z_adjoin_w a = P[i + j + len * 0];
                Z_adjoin_w b = P[i + j + len * 1];
                Z_adjoin_w c = P[i + j + len * 2];
                if (invert == 0) {
                    P[i + j + len * 0] = add(a, add(b, c));
                    P[i + j + len * 1] = add(a, add(mul(b, w), mul(c, w2)));
                    P[i + j + len * 2] = add(a, add(mul(b, w2), mul(c, w)));
                } else {
                    P[i + j + len * 0] = div_by_3(add(a, add(b, c)));
                    P[i + j + len * 1] = div_by_3(add(a, add(mul(b, w2), mul(c, w))));
                    P[i + j + len * 2] = div_by_3(add(a, add(mul(b, w), mul(c, w2))));
                }
            }
        }
    }
}

void calc () {
    int siz = 1;
    for (int i = 0; i < k; i++) siz *= 3;

    modified_FWHT(0);
    for (int i = 0; i < siz; i++) {
        P[i] = mul(P[i], P[i]);
    }
    modified_FWHT(1);

    int sol = 0;
    for (int i = 0; i < siz; i++) {
        int val = i, comp = 0, pot = 1;
        for (int j = 0; j < k; j++) {
            comp += (3 - val % 3) % 3 * pot;
            val /= 3;
            pot *= 3;
        }
        sol += cnt[i] * (P[comp].x - 1);
    }
    cout << sol / 6;
}

signed main () {
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);
    scanf("%d%d", &n, &k);
    getchar();
    for (int i = 0; i < n; i++) {

        int val = 0;
        for (int j = 0; j < k; j++) {
            char c = getchar();
            val = val * 3 + c - '1';
        }
        getchar();

        P[val] = Z_adjoin_w(1, 0);
        cnt[val]++;
    }
    calc();
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:107:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  107 |     scanf("%d%d", &n, &k);
      |            ~^     ~~
      |             |     |
      |             int*  long long int*
      |            %lld
Main.cpp:107:15: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
  107 |     scanf("%d%d", &n, &k);
      |              ~^       ~~
      |               |       |
      |               int*    long long int*
      |              %lld
Main.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 17040 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 17004 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 3 ms 17236 KB Output is correct
11 Correct 3 ms 16984 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 3 ms 17016 KB Output is correct
14 Correct 3 ms 16988 KB Output is correct
15 Correct 3 ms 16988 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 17040 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 17004 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 3 ms 17236 KB Output is correct
11 Correct 3 ms 16984 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 3 ms 17016 KB Output is correct
14 Correct 3 ms 16988 KB Output is correct
15 Correct 3 ms 16988 KB Output is correct
16 Correct 3 ms 17044 KB Output is correct
17 Correct 3 ms 17024 KB Output is correct
18 Correct 3 ms 17004 KB Output is correct
19 Correct 3 ms 17236 KB Output is correct
20 Correct 3 ms 16988 KB Output is correct
21 Correct 3 ms 16988 KB Output is correct
22 Correct 3 ms 16988 KB Output is correct
23 Correct 3 ms 16984 KB Output is correct
24 Correct 3 ms 16988 KB Output is correct
25 Correct 4 ms 16988 KB Output is correct
26 Correct 3 ms 16988 KB Output is correct
27 Correct 3 ms 16988 KB Output is correct
28 Correct 3 ms 16988 KB Output is correct
29 Correct 3 ms 16988 KB Output is correct
30 Correct 3 ms 17044 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 17040 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 17004 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 3 ms 17236 KB Output is correct
11 Correct 3 ms 16984 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 3 ms 17016 KB Output is correct
14 Correct 3 ms 16988 KB Output is correct
15 Correct 3 ms 16988 KB Output is correct
16 Correct 3 ms 17044 KB Output is correct
17 Correct 3 ms 17024 KB Output is correct
18 Correct 3 ms 17004 KB Output is correct
19 Correct 3 ms 17236 KB Output is correct
20 Correct 3 ms 16988 KB Output is correct
21 Correct 3 ms 16988 KB Output is correct
22 Correct 3 ms 16988 KB Output is correct
23 Correct 3 ms 16984 KB Output is correct
24 Correct 3 ms 16988 KB Output is correct
25 Correct 4 ms 16988 KB Output is correct
26 Correct 3 ms 16988 KB Output is correct
27 Correct 3 ms 16988 KB Output is correct
28 Correct 3 ms 16988 KB Output is correct
29 Correct 3 ms 16988 KB Output is correct
30 Correct 3 ms 17044 KB Output is correct
31 Correct 56 ms 19036 KB Output is correct
32 Correct 56 ms 19036 KB Output is correct
33 Correct 50 ms 19032 KB Output is correct
34 Correct 124 ms 27732 KB Output is correct
35 Correct 3 ms 16988 KB Output is correct
36 Correct 3 ms 16988 KB Output is correct
37 Correct 3 ms 16988 KB Output is correct
38 Correct 85 ms 27148 KB Output is correct
39 Correct 65 ms 22620 KB Output is correct
40 Correct 83 ms 26960 KB Output is correct
41 Correct 59 ms 21644 KB Output is correct
42 Correct 85 ms 27012 KB Output is correct
43 Correct 4 ms 16984 KB Output is correct
44 Correct 3 ms 16988 KB Output is correct
45 Correct 3 ms 16988 KB Output is correct