Submission #1228813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228813		12345678	Mosaic (IOI24_mosaic)	C++20	0 / 100	480 ms	357392 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5, kx=105;

ll n, q, r[nx][kx], c[kx][nx], C=100;
map<ll, ll> mp;

std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y,
                              std::vector<int> T, std::vector<int> B,
                              std::vector<int> L, std::vector<int> R) {
    n=X.size(), q=T.size();
    C=min(C, n);
    for (int i=0; i<n; i++) r[i][0]=Y[i], c[0][i]=X[i];
    for (int i=0; i<C; i++) r[0][i]=X[i], c[i][0]=Y[i];
    for (int i=1; i<n; i++) for (int j=1; j<C; j++) r[i][j]=!(r[i-1][j]||r[i][j-1]);
    for (int i=1; i<C; i++) for (int j=1; j<n; j++) c[i][j]=!(c[i-1][j]||c[i][j-1]);
    for (int i=C-1; i<n; i++) mp[i-(C-1)]=r[i][C-1], mp[(C-1)-i]=c[C-1][i];
    std::vector<long long> res(q);
    for (int i=0; i<q; i++)
    {
        if (T[i]<C) res[i]=r[T[i]][L[i]];
        else if (L[i]<C) res[i]=c[L[i]][T[i]];
        else res[i]=mp[T[i]-L[i]];
    }
    return res;
}

/*
4
1 0 1 0
1 1 0 1
2
0 1 0 1
2 3 2 3

*/

• 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