Submission #65426697


Source Code Expand

#include <bits/stdc++.h>

// what the fuck
template<typename T, int N>
struct NDVector { using type = std::vector<typename NDVector<T, N - 1>::type>; };
template<typename T>
struct NDVector<T, 1> { using type = std::vector<T>; };

// A tensor is essentially a vector of tensors. (or multidimensional array)
template<typename T, int N>
using Tensor = typename NDVector<T, N>::type;

/**
 * Create a multidimensional vector with the given dimension sizes.
 *
 * In particular, create_vector(N) = create_tensor(N), create_matrix(N, M) = create_tensor(N, M).
 * If you have some weird multidimensional DP, you can create the DP table by doing:
 *      dp = create_tensor(5, 5, 5, 5, 5);
 *
 * Be careful, for a large number of dimensions, this uses a lot of memory and is very cache unfriendly.
 */
template<typename T>
std::vector<T> create_tensor(int N) {
    return std::vector<T>(N);
}
template <typename T, typename... ArgTypes>
Tensor<T, sizeof...(ArgTypes) + 1> create_tensor(int N, ArgTypes... args) {
    auto under = create_tensor<T>(args...);
    return std::vector(N, under);
}

/**
 * Create a matrix of the given dimensions.
 */
template<typename T>
Tensor<T, 2> create_matrix(int N, int M) {
    return create_tensor<T>(N, M);
}

/**
 * Frequently used definitions, like Vector, Matrices, pairs of ints, pairs, triples, etc.
 */
template<typename T>
using Vector = Tensor<T, 1>; // I could use std::vector<T>, but this is just too cool.
template<typename T>
using Matrix = Tensor<T, 2>;

template<typename T1, typename T2>
using Pair = std::pair<T1, T2>;
using PairII = Pair<int, int>;
using PairLL = Pair<long long, long long>;

template<typename T1, typename T2, typename T3>
using Triple = std::tuple<T1, T2, T3>;

/**
 * Read a vector from input. Set start to 1 if you want it to be 1-indexed.
 */
template<typename T>
Vector<T> read_vector(int N, int start = 0) {
    Vector<T> v(start + N);
    for (int i = start; i < (int)v.size(); i++) {
        std::cin >> v[i];
    }
    return v;
}

/**
 * Read a matrix from input. Set start_l to make lines 1-indexed. Same thing for start_c.
 */
template<typename T>
Matrix<T> read_matrix(int N, int M, int start_l = 0, int start_c = 0) {
    Matrix<T> matr = create_matrix<T>(N + start_l, M + start_c);

    for (int l = start_l; l < N + start_l; l++)
        for (int c = start_c; c < M + start_c; c++)
            std::cin >> matr[l][c];

    return matr;
}

/**
 * Print a tensor to the output stream. Prints all indices between i and j, and the elements 
 * are separated by the given separator.
 *
 * To generalize, for each dimension, you give the bounds that you want to print and the separator
 * between each order. To print a matrix, you would do:
 *
 *      print_tensor(matr, std::cout, 0, N - 1, "\n", 0, M - 1, " ");
 */
template<typename T>
void print_tensor(Tensor<T, 1>& tens, std::ostream&fout, int i, int j, const char* sep) {
    for (int t = std::max(i, 0); t <= j && t < (int)tens.size(); t++) {
        fout << tens[t];
        if (t + 1 <= j)
            fout << sep;
    }
}

template<typename T, typename... Sizes>
void print_tensor(
        Tensor<T, sizeof...(Sizes) / 3 + 1>& tens,
        std::ostream& fout, 
        int i, int j, const char* sep, Sizes... sizes) {
    for (int t = std::max(i, 0); t <= j && t < (int)tens.size(); t++) {
        print_tensor<T>(tens[t], fout, sizes...);
        if (t + 1 <= j)
            fout << sep;
    }
}

/**
 * Print a vector to the given output stream with given bounds and separator.
 */
template<typename T>
void print_vector(std::vector<T>& v, std::ostream& fout, int i = 0, int j = (1 << 30), const char* sep = " ") {
    print_tensor<T>(v, fout, i, j, sep);
}

/**
 * Read a vector of pairs. Set start to 1 if you want this to be 1-indexed.
 */
template<typename T1, typename T2>
Vector<Pair<T1, T2>> read_pairvec(int N, int start = 0) {
    Vector<Pair<T1, T2>> input = Vector<Pair<T1, T2>>(start + N);
    for (int i = start; i < start + N; i++)
        std::cin >> input[i].first >> input[i].second;
    return input;
}

/**
 * Read a vector of triples. Set start to 1 if you want this to be 1-indexed.
 *
 * If you need higher order tuples, like quadruples, you're better off using a matrix instead.
 */
template<typename T1, typename T2, typename T3>
Vector<Triple<T1, T2, T3>> read_triplevec(int N, int start = 0) {
    Vector<Triple<T1, T2, T3>> input = Vector<Triple<T1, T2, T3>>(start + N);
    for (int i = start; i < N + start; i++) {
        T1 a;
        T2 b;
        T3 c;
        std::cin >> a >> b >> c;
        input[i] = {a, b, c};
    }
    return input;
}

/**
 * Solve a testcase of the problem. You will code your solution here instead of main.
 */
void solve_test();

/**
 * Call this function if you have a problem with multiple testcases.
 */
void multitest_problem() {
    int T;
    std::cin >> T;

    while (T--) solve_test();
}

int main() {
    std::cin.tie(NULL);
    std::iostream::sync_with_stdio(false);

    // Choose one of the following functions, depending on the problem type.
    solve_test();
    //multitest_problem();

    return 0;
}

void solve_test() {
    int N;
    std::cin >> N;

    auto S = read_vector<std::string>(N);
    auto T = read_vector<std::string>(N);

    auto rotate = [&]() {
        auto res = Vector<std::string>(N);
        for (int i = 0; i < N; i++)
            res[i] = std::string(N, '.');

        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++) {
                res[j][N - i - 1] = S[i][j];
            }

        S = res;
    };

    int res = 1 << 30;
    for (int i = 0; i < 4; i++) {
        int local = i;
        for (int l = 0; l < N; l++)
            for (int c = 0; c < N; c++)
                if (S[l][c] != T[l][c])
                    local++;
        res = std::min(res, local);
        rotate();
    }

    std::cout << res;
}



Submission Info

Submission Time
Task B - Grid Rotation
User Tinca_Matei
Language C++ 20 (gcc 12.2)
Score 250
Code Size 6090 Byte
Status AC
Exec Time 1 ms
Memory 3612 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 250 / 250
Status
AC × 2
AC × 21
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
random_01.txt AC 1 ms 3612 KiB
random_02.txt AC 1 ms 3480 KiB
random_03.txt AC 1 ms 3464 KiB
random_04.txt AC 1 ms 3436 KiB
random_05.txt AC 1 ms 3404 KiB
random_06.txt AC 1 ms 3444 KiB
random_07.txt AC 1 ms 3492 KiB
random_08.txt AC 1 ms 3356 KiB
random_09.txt AC 1 ms 3440 KiB
random_10.txt AC 1 ms 3576 KiB
random_11.txt AC 1 ms 3520 KiB
random_12.txt AC 1 ms 3484 KiB
random_13.txt AC 1 ms 3432 KiB
random_14.txt AC 1 ms 3528 KiB
random_15.txt AC 1 ms 3520 KiB
random_16.txt AC 1 ms 3528 KiB
random_17.txt AC 1 ms 3476 KiB
random_18.txt AC 1 ms 3328 KiB
random_19.txt AC 1 ms 3604 KiB
sample_01.txt AC 1 ms 3472 KiB
sample_02.txt AC 1 ms 3460 KiB