oj.uz

Submission #512294

# Submission time Handle Problem Language Result Execution time Memory
512294 2022-01-16T08:58:51 Z KoD Tenis (COCI20_tenis) C++17
110 / 110
 63 ms 5464 KB 
#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<array<int, 3>> order(N);
    vector<array<int, 3>> rank(N);
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < N; ++j) {
            std::cin >> order[j][i];
            order[j][i] -= 1;
            rank[order[j][i]][i] = j;
        }
    }
    array<int, 6> remain = {};
    const auto add = [&](const int x, const int c) {
        array<int, 3> ord = {0, 1, 2};
        int i = 0;
        do {
            if (std::is_sorted(ord.begin(), ord.end(), [&](const int i, const int j) {
                if (rank[x][i] != rank[x][j]) return rank[x][i] < rank[x][j];
                return i < j;
            })) {
                remain[i] += c;
                break;
            }
            i += 1;
        } while (std::next_permutation(ord.begin(), ord.end()));
    };
    for (int i = 0; i < N; ++i) {
        add(i, 1);
    }
    array<long long, 3> play = {};
    vector<int> win(N);
    vector<char> done(N);
    const auto court = [&](const int i, const int j) {
        tuple tup(N, N, 3);
        for (int k = 0; k < 3; ++k) {
            tup = std::min(tup, tuple(std::min(rank[i][k], rank[j][k]), std::max(rank[i][k], rank[j][k]), k));
        }
        return std::get<2>(tup);
    };
    for (int i = 0; i < N; ++i) {
        std::map<int, vector<int>> here;
        for (int j = 0; j < 3; ++j) {
            const int x = order[i][j];
            if (!done[x]) here[x].push_back(j);
        }
        for (const auto& [x, v] : here) {
            add(x, -1);
            done[x] = true;
            for (const auto& [y, u] : here) {
                if (x < y) {
                    const int j = court(x, y);
                    play[j] += 1;
                    win[rank[x][j] < rank[y][j] ? x : y] += 1;
                }
            }
        }
        for (const auto& [x, v] : here) {
            array<int, 3> ord = {0, 1, 2};
            int k = 0;
            do {
                for (const int j : ord) {
                    if (std::binary_search(v.begin(), v.end(), j)) {
                        play[j] += remain[k];
                        win[x] += remain[k];
                        break;
                    }
                }
                k += 1;
            } while (std::next_permutation(ord.begin(), ord.end()));
        }
    }
    for (int i = 0; i < 3; ++i) {
        std::cout << play[i] << " \n"[i + 1 == 3];
    }
    for (int i = 0; i < N; ++i) {
        std::cout << win[i] << " \n"[i + 1 == N];
    }
    return 0;
}

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 3 ms 460 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 22 ms 2252 KB Output is correct
6 Correct 34 ms 3476 KB Output is correct
7 Correct 44 ms 4344 KB Output is correct
8 Correct 63 ms 5464 KB Output is correct
9 Correct 56 ms 5456 KB Output is correct
10 Correct 49 ms 5460 KB Output is correct