Submission #1129983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129983		math_rabbit_1028	Mosaic (IOI24_mosaic)	C++20	0 / 100	118 ms	16096 KiB

mosaic

#include "mosaic.h"
using namespace std;

vector<int> X2, Y2;
vector<int> diag; // X - Y
vector<int> inv;

int color(int a, int b) {
    if (a == 0 && b == 0) return 1;
    else return 0;
}

vector<long long> mosaic(vector<int> X, vector<int> Y,
                         vector<int> T, vector<int> B,
                         vector<int> L, vector<int> R) {
    int N = (int)X.size();
    int Q = (int)T.size();

    if (N == 1) {
        return vector<long long>(Q, X[0]);
    }

    if (X[1] == 0 && Y[1] == 0) {
        X2.push_back(Y[1]);
        for (int i = 1; i < N; i++) X2.push_back(color(X2.back(), X[i]));
        Y2.push_back(X[1]);
        for (int i = 1; i < N; i++) Y2.push_back(color(Y2.back(), Y[i]));
        for (int i = 0; i <= 2*N; i++) {
            if (abs(i - N) % 2 == 0) diag.push_back(1);
            else diag.push_back(0);
        }

        inv = vector<int>(2*N+1, 0);
        int p = 3;
        while (p < N) {
            if (X[p] == 1) {
                if (p+1 < N && X[p+1] == 1) p += 2;
                else {
                    inv[N-(p-1)] = 1;
                    p += 3;
                }
            }
            else p += 2;
        }
        p = 3;
        while (p < N) {
            if (Y[p] == 1) {
                if (p+1 < N && Y[p+1] == 1) p += 2;
                else {
                    inv[N+(p-1)] = 1;
                    p += 3;
                }
            }
            else p += 2;
        }

        for (int i = N+1; i <= 2*N; i++) inv[i] += inv[i-1];
        for (int i = N-1; i >= 0; i--) inv[i] += inv[i+1];
        for (int i = 0; i <= 2*N; i++) diag[i] = (diag[i] + inv[i]) % 2;
    }
    else {
        X2.push_back(Y[1]);
        for (int i = 1; i < N; i++) X2.push_back(color(X2.back(), X[i]));
        Y2.push_back(X[1]);
        for (int i = 1; i < N; i++) Y2.push_back(color(Y2.back(), Y[i]));        
        for (int i = 0; i <= 2*N; i++) {
            if (abs(i - N) % 2 == 1) diag.push_back(1);
            else diag.push_back(0);
        }

        inv = vector<int>(2*N+1, 0);
        int p = 2;
        while (p < N) {
            if (X[p] == 1) {
                if (p+1 < N && X[p+1] == 1) p += 2;
                else {
                    inv[N-(p-1)] = 1;
                    p += 3;
                }
            }
            else p += 2;
        }
        p = 2;
        while (p < N) {
            if (Y[p] == 1) {
                if (p+1 < N && Y[p+1] == 1) p += 2;
                else {
                    inv[N+(p-1)] = 1;
                    p += 3;
                }
            }
            else p += 2;
        }

        for (int i = N+1; i <= 2*N; i++) inv[i] += inv[i-1];
        for (int i = N-1; i >= 0; i--) inv[i] += inv[i+1];
        for (int i = 0; i <= 2*N; i++) diag[i] = (diag[i] + inv[i]) % 2;
    }

    vector<long long> C(Q, 0);
    for (int i = 0; i < Q; i++) {
        if (T[i] == 0) {
            C[i] = X[L[i]];
        }
        else if (T[i] == 1) {
            C[i] = X2[L[i]];
        }
        else if (L[i] == 0) {
            C[i] = Y[T[i]];
        }
        else if (L[i] == 1) {
            C[i] = Y2[T[i]];
        }
        else {
            C[i] = diag[N+T[i]-L[i]];
        }
    }

    return C;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 8
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22