Submission #1165918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165918		aminabouakaz	Pyramids (IOI24_pyramids)	C++20	20 / 100	59 ms	21416 KiB

pyramids

#include <vector>
using namespace std;

vector<int> prefixSumA, prefixSumB;
vector<vector<int>> prefixCountA, prefixCountB;

void init(vector<int> A, vector<int> B) {
    int N = A.size();
    prefixSumA.resize(N);
    prefixSumB.resize(N);
    prefixCountA.assign(N, vector<int>(11, 0));
    prefixCountB.assign(N, vector<int>(11, 0));

    prefixSumA[0] = A[0];
    prefixSumB[0] = B[0];
    prefixCountA[0][A[0]] = 1;
    prefixCountB[0][B[0]] = 1;

    for (int i = 1; i < N; ++i) {
        prefixSumA[i] = prefixSumA[i - 1] + A[i];
        prefixSumB[i] = prefixSumB[i - 1] + B[i];
        for (int j = 1; j <= 10; ++j) {
            prefixCountA[i][j] = prefixCountA[i - 1][j];
            prefixCountB[i][j] = prefixCountB[i - 1][j];
        }
        prefixCountA[i][A[i]]++;
        prefixCountB[i][B[i]]++;
    }
}

bool can_transform(int L, int R, int X, int Y) {
    int sumA = prefixSumA[R] - (L > 0 ? prefixSumA[L - 1] : 0);
    int sumB = prefixSumB[Y] - (X > 0 ? prefixSumB[X - 1] : 0);
    if (sumA != sumB) {
        return false;
    }

    vector<int> countA(11, 0), countB(11, 0);
    for (int i = 1; i <= 10; ++i) {
        countA[i] = prefixCountA[R][i] - (L > 0 ? prefixCountA[L - 1][i] : 0);
        countB[i] = prefixCountB[Y][i] - (X > 0 ? prefixCountB[X - 1][i] : 0);
    }

    return countA == countB;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 20 / 20
• Subtask 4: 0 / 30