[tutorial:754A]↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main() {↵
int n;↵
scanf("%d", &n);↵
vector<int> a(n);↵
long long sum = 0;↵
for (int & x : a) {↵
scanf("%d", &x);↵
sum += x;↵
}↵
if (sum != 0) {↵
puts("YES");↵
puts("1");↵
printf("%d %d\n", 1, n);↵
exit(0);↵
}↵
sum = 0;↵
for (int i = 0; i < n; i++) {↵
sum += a[i];↵
if (sum != 0) {↵
puts("YES");↵
puts("2");↵
printf("%d %d\n", 1, i + 1);↵
printf("%d %d\n", i + 2, n);↵
exit(0);↵
}↵
}↵
puts("NO");↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:754B]↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main() {↵
char str[4][4 + 1];↵
// cells are '.', 'o', 'x'↵
for (int i = 0; i < 4; i++) {↵
cin >> str[i];↵
}↵
↵
auto check = [&]() {↵
for (int i = 0; i < 4; i++) {↵
for (int j = 0; j < 4; j++) {↵
for (int dx = -1; dx <= 1; dx++) {↵
for (int dy = -1; dy <= 1; dy++) {↵
if (dx == 0 && dy == 0) continue;↵
if (i + dx * 3 > 4 || j + dy * 3 > 4 || i + dx * 3 < -1 || j + dy * 3 < -1) continue;↵
bool ok = true;↵
for (int p = 0; p < 3; p++) {↵
ok &= str[i + p * dx][j + p * dy] == 'x';↵
}↵
if (ok) return true;↵
}↵
}↵
}↵
}↵
return false;↵
};↵
↵
for (int i = 0; i < 4; i++) {↵
for (int j = 0; j < 4; j++) {↵
if (str[i][j] == '.') {↵
str[i][j] = 'x';↵
if (check()) {↵
puts("YES");↵
exit(0);↵
}↵
str[i][j] = '.';↵
}↵
}↵
}↵
puts("NO");↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[tutorial:754C]↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
#define all(x) (x).begin(), (x).end()↵
↵
void solve() {↵
int n;↵
cin >> n;↵
vector<string> names(n);↵
for (string& name : names) {↵
cin >> name;↵
}↵
sort(all(names));↵
↵
auto getIdx = [&](const string& s) {↵
int pos = lower_bound(all(names), s) - names.begin();↵
if (pos == (int)names.size() || names[pos] != s) return -1;↵
return pos;↵
};↵
↵
auto splitIntoUserMessage = [](const string& s) {↵
size_t pos = s.find(':');↵
assert(pos != string::npos);↵
return make_pair(s.substr(0, pos), s.substr(pos + 1));↵
};↵
↵
auto splitIntoTokensOfLatinLetters = [](const string& s) {↵
vector<string> result;↵
string token;↵
for (char c : s) {↵
if (isalpha(c) || isdigit(c)) {↵
token += c;↵
}↵
else {↵
if (!token.empty()) {↵
result.push_back(token);↵
}↵
token.clear();↵
}↵
}↵
if (!token.empty()) {↵
result.push_back(token);↵
}↵
return result;↵
};↵
↵
int m;↵
cin >> m;↵
vector<int> who(m);↵
vector<vector<char>> can(m, vector<char>(n, true));↵
↵
vector<string> messages(m);↵
↵
string tmp;↵
getline(cin, tmp);↵
↵
for (int i = 0; i < m; i++) {↵
string cur;↵
getline(cin, cur);↵
pair<string, string> p = splitIntoUserMessage(cur);↵
const string& user = p.first;↵
const string& message = p.second;↵
who[i] = getIdx(user);↵
if (who[i] != -1) {↵
fill(all(can[i]), false);↵
can[i][who[i]] = true;↵
}↵
messages[i] = message;↵
vector<string> tokens = splitIntoTokensOfLatinLetters(message);↵
for (const string& z : tokens) {↵
int idx = getIdx(z);↵
if (idx != -1) {↵
can[i][idx] = false;↵
}↵
}↵
}↵
↵
vector<vector<int>> par(m, vector<int>(n, -1));↵
for (int i = 0; i < n; i++) {↵
if (can[0][i]) par[0][i] = 0;↵
}↵
for (int msg = 0; msg + 1 < m; msg++) {↵
for (int i = 0; i < n; i++) {↵
if (par[msg][i] == -1) continue;↵
for (int j = 0; j < n; j++) {↵
if (i == j) continue;↵
if (can[msg + 1][j]) {↵
par[msg + 1][j] = i;↵
}↵
}↵
}↵
}↵
int msg = m - 1, pos = -1;↵
for (int i = 0; i < n; i++) {↵
if (par[msg][i] != -1) {↵
pos = i;↵
break;↵
}↵
}↵
if (pos == -1) {↵
cout << "Impossible\n";↵
return;↵
}↵
while (msg >= 0) {↵
who[msg] = pos;↵
pos = par[msg][pos];↵
msg--;↵
}↵
for (int i = 0; i < m; i++) {↵
cout << names[who[i]] << ":" << messages[i] << "\n";↵
}↵
return;↵
}↵
↵
int main() {↵
//freopen("input.txt", "r", stdin);↵
int t;↵
cin >> t; // number of tests↵
↵
while (t--) {↵
solve();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[tutorial:754D]↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
typedef long long ll;↵
↵
int nextInt() {↵
int x = 0, p = 1;↵
char c;↵
do {↵
c = getchar();↵
} while (c <= 32);↵
if (c == '-') {↵
p = -1;↵
c = getchar();↵
}↵
while (c >= '0' && c <= '9') {↵
x = x * 10 + c - '0';↵
c = getchar();↵
}↵
return x * p;↵
}↵
↵
#define all(x) (x).begin(), (x).end()↵
↵
const int N = (int)3e5 + 5;↵
const int MAX_VAL = (int)1e9;↵
↵
int n;↵
ll l[N], r[N];↵
↵
struct event {↵
ll x;↵
int c;↵
event() {}↵
event(ll x, int c) : x(x), c(c) {}↵
};↵
↵
pair<ll, int> check(ll len) {↵
if (len == 0) return make_pair(0LL, n);↵
static vector<event> evs;↵
evs.resize(0);↵
for (int i = 1; i <= n; i++) {↵
if (r[i] - len > l[i]) {↵
evs.push_back(event(l[i], 1));↵
evs.push_back(event(r[i] - len, -1));↵
}↵
}↵
sort(all(evs), [](const event & a, const event & b) { return a.x < b.x; });↵
reverse(all(evs));↵
int cnt = 0, maxiCnt = 0;↵
ll bestPos = 0;↵
while (evs.size() > 0) {↵
ll x = evs.back().x;↵
while (evs.size() > 0 && evs.back().x == x) {↵
cnt += evs.back().c;↵
evs.pop_back();↵
}↵
if (cnt > maxiCnt) {↵
maxiCnt = cnt;↵
bestPos = x;↵
}↵
}↵
return make_pair(bestPos, maxiCnt);↵
}↵
↵
vector<int> getAns(ll len) {↵
if (len == 0) {↵
vector<int> res(n);↵
iota(all(res), 1);↵
return res;↵
}↵
ll pos = check(len).first;↵
vector<int> res;↵
for (int i = 1; i <= n; i++) {↵
if (pos >= l[i] && pos < r[i] - len) {↵
res.push_back(i);↵
}↵
}↵
return res;↵
}↵
↵
int main() {↵
n = nextInt();↵
int k = nextInt();↵
for (int i = 1; i <= n; i++) {↵
l[i] = nextInt();↵
r[i] = nextInt() + 2;↵
}↵
ll l = 0, r = MAX_VAL + MAX_VAL + 5;↵
while (r - l > 1) {↵
ll mid = (l + r) >> 1;↵
if (check(mid).second >= k) l = mid;↵
else r = mid;↵
}↵
↵
vector<int> ans = getAns(l);↵
↵
cout << l << endl;↵
assert((int)ans.size() >= k);↵
ans.resize(k);↵
for (int i : ans) {↵
printf("%d ", i);↵
}↵
puts("");↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:754E]↵
↵
<spoiler summary="C++ code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
const int N = (int)404;↵
const int ALPHA = 26;↵
↵
bitset<N> b[ALPHA][N];↵
char patt[N][N];↵
bitset<N> result[N];↵
↵
bitset<N> getShifted(const bitset<N>& b, int len, int shift) {↵
assert(0 <= shift && shift < len);↵
return (b >> shift) | (b << (len - shift));↵
}↵
↵
int main() {↵
#ifdef LOCAL↵
freopen("input.txt", "r", stdin);↵
#endif↵
int n, m, r, c;↵
scanf("%d%d", &n, &m);↵
↵
for (int i = 0; i < n; i++) {↵
static char str[N];↵
scanf("%s", str);↵
for (int j = 0; j < m; j++) {↵
b[(int)(str[j] - 'a')][i][j] = true;↵
}↵
}↵
↵
scanf("%d%d", &r, &c);↵
↵
for (int i = 0; i < n; i++) {↵
result[i] = ~result[i];↵
}↵
↵
for (int i = 0; i < r; i++) {↵
scanf("%s", patt[i]);↵
for (int j = 0; j < c; j++) {↵
if (patt[i][j] == '?') continue;↵
int c = patt[i][j] - 'a';↵
int shiftByX = (((-i) % n) + n) % n;↵
int shiftByY = (((j) % m) + m) % m;↵
for (int x = 0; x < n; x++) {↵
int nx = (x + shiftByX);↵
if (nx >= n) nx -= n;↵
result[nx] &= getShifted(b[c][x], m, shiftByY);↵
}↵
}↵
}↵
↵
for (int i = 0; i < n; i++) {↵
for (int j = 0; j < m; j++) {↵
putchar(result[i][j] ? '1' : '0');↵
}↵
puts("");↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Java code">↵
↵
~~~~~↵
import java.io.*;↵
import java.util.*;↵
↵
public class Main {↵
↵
static class InputReader {↵
BufferedReader bufferedReader;↵
StringTokenizer stringTokenizer;↵
InputReader(InputStream inputStream) {↵
bufferedReader = new BufferedReader(new InputStreamReader(inputStream), 32768);↵
stringTokenizer = null;↵
}↵
String next() {↵
while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {↵
try {↵
stringTokenizer = new StringTokenizer(bufferedReader.readLine());↵
} catch (IOException ex) {↵
ex.printStackTrace();↵
throw new RuntimeException(ex);↵
}↵
}↵
return stringTokenizer.nextToken();↵
}↵
int nextInt() {↵
return Integer.parseInt(next());↵
}↵
long nextLong() {↵
return Long.parseLong(next());↵
}↵
double nextDouble() {↵
return Double.parseDouble(next());↵
}↵
}↵
↵
static int[] newBitSet(int n) {↵
return new int[(n + 31) / 32];↵
}↵
↵
static void setBit(int[] a, int pos) {↵
a[pos >>> 5] |= (1 << (pos & 31));↵
}↵
↵
static boolean getBit(int[] a, int pos) {↵
return ((a[pos >>> 5]) & (1 << (pos & 31))) != 0;↵
}↵
↵
static void setAll(int[] a) {↵
for (int i = 0; i < a.length; i++) {↵
a[i] = ~0;↵
}↵
}↵
↵
static void resetAll(int[] a) {↵
for (int i = 0; i < a.length; i++) {↵
a[i] = 0;↵
}↵
}↵
↵
static void andXYtoX(int[] x, int[] y) {↵
for (int i = 0; i < x.length; i++) {↵
x[i] &= y[i];↵
}↵
}↵
↵
static void leftShiftAndOr(int ch, int shift, int x, int[][][][] shl, int[] to) {↵
int[] z = shl[ch][shift & 31][x];↵
int delta = (shift >>> 5);↵
for (int i = delta; i < to.length; i++) {↵
to[i - delta] |= z[i];↵
}↵
}↵
↵
static void rightShiftAndOr(int ch, int shift, int x, int[][][][] shr, int[] to) {↵
int[] z = shr[ch][shift & 31][x];↵
int delta = (shift >>> 5);↵
for (int i = 0; i + delta < to.length; i++) {↵
to[i + delta] |= z[i];↵
}↵
}↵
↵
static void printBitset(int a[], int l, int r) {↵
for (int i = l; i <= r; i++) {↵
System.err.print(getBit(a, i) ? '1' : '0');↵
}↵
System.err.println();↵
}↵
↵
static final int ALPHA = 26;↵
↵
public static void main(String[] args) {↵
InputReader in = new InputReader(System.in);↵
PrintWriter out = new PrintWriter(System.out);↵
↵
int n = in.nextInt();↵
int m = in.nextInt();↵
↵
int[][][][] shl = new int[ALPHA][32][n][];↵
int[][][][] shr = new int[ALPHA][32][n][];↵
↵
for (int c = 0; c < ALPHA; c++) {↵
for (int sh = 0; sh < 32; sh++) {↵
for (int i = 0; i < n; i++) {↵
shl[c][sh][i] = newBitSet(m);↵
shr[c][sh][i] = newBitSet(m);↵
}↵
}↵
}↵
↵
String[] s = new String[n];↵
↵
for (int i = 0; i < n; i++) {↵
s[i] = in.next();↵
for (int j = 0; j < m; j++) {↵
int c = s[i].charAt(j) - 'a';↵
for (int sh = 0; sh < 32; sh++) {↵
if (j - sh >= 0) {↵
setBit(shl[c][sh][i], j - sh);↵
}↵
if (j + sh < m) {↵
setBit(shr[c][sh][i], j + sh);↵
}↵
}↵
}↵
}↵
↵
int r = in.nextInt();↵
int c = in.nextInt();↵
↵
String[] patt = new String[r];↵
↵
int[][] res = new int[n][];↵
↵
for (int i = 0; i < n; i++) {↵
res[i] = newBitSet(m);↵
setAll(res[i]);↵
}↵
↵
int[] tmp = newBitSet(m);↵
↵
for (int i = 0; i < r; i++) {↵
patt[i] = in.next();↵
for (int j = 0; j < c; j++) {↵
if (patt[i].charAt(j) == '?') continue;↵
int cur = patt[i].charAt(j) - 'a';↵
int shiftByX = (((-i) % n) + n) % n;↵
int shiftByY = (((j) % m) + m) % m;↵
↵
for (int x = 0; x < n; x++) {↵
int nx = x + shiftByX;↵
if (nx >= n) nx -= n;↵
resetAll(tmp);↵
leftShiftAndOr(cur, shiftByY, x, shl, tmp);↵
rightShiftAndOr(cur, m - shiftByY, x, shr, tmp);↵
andXYtoX(res[nx], tmp);↵
}↵
}↵
}↵
↵
for (int i = 0; i < n; i++) {↵
for (int j = 0; j < m; j++) {↵
out.print(getBit(res[i], j) ? '1' : '0');↵
}↵
out.println();↵
}↵
↵
out.close();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main() {↵
int n;↵
scanf("%d", &n);↵
vector<int> a(n);↵
long long sum = 0;↵
for (int & x : a) {↵
scanf("%d", &x);↵
sum += x;↵
}↵
if (sum != 0) {↵
puts("YES");↵
puts("1");↵
printf("%d %d\n", 1, n);↵
exit(0);↵
}↵
sum = 0;↵
for (int i = 0; i < n; i++) {↵
sum += a[i];↵
if (sum != 0) {↵
puts("YES");↵
puts("2");↵
printf("%d %d\n", 1, i + 1);↵
printf("%d %d\n", i + 2, n);↵
exit(0);↵
}↵
}↵
puts("NO");↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:754B]↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main() {↵
char str[4][4 + 1];↵
// cells are '.', 'o', 'x'↵
for (int i = 0; i < 4; i++) {↵
cin >> str[i];↵
}↵
↵
auto check = [&]() {↵
for (int i = 0; i < 4; i++) {↵
for (int j = 0; j < 4; j++) {↵
for (int dx = -1; dx <= 1; dx++) {↵
for (int dy = -1; dy <= 1; dy++) {↵
if (dx == 0 && dy == 0) continue;↵
if (i + dx * 3 > 4 || j + dy * 3 > 4 || i + dx * 3 < -1 || j + dy * 3 < -1) continue;↵
bool ok = true;↵
for (int p = 0; p < 3; p++) {↵
ok &= str[i + p * dx][j + p * dy] == 'x';↵
}↵
if (ok) return true;↵
}↵
}↵
}↵
}↵
return false;↵
};↵
↵
for (int i = 0; i < 4; i++) {↵
for (int j = 0; j < 4; j++) {↵
if (str[i][j] == '.') {↵
str[i][j] = 'x';↵
if (check()) {↵
puts("YES");↵
exit(0);↵
}↵
str[i][j] = '.';↵
}↵
}↵
}↵
puts("NO");↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[tutorial:754C]↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
#define all(x) (x).begin(), (x).end()↵
↵
void solve() {↵
int n;↵
cin >> n;↵
vector<string> names(n);↵
for (string& name : names) {↵
cin >> name;↵
}↵
sort(all(names));↵
↵
auto getIdx = [&](const string& s) {↵
int pos = lower_bound(all(names), s) - names.begin();↵
if (pos == (int)names.size() || names[pos] != s) return -1;↵
return pos;↵
};↵
↵
auto splitIntoUserMessage = [](const string& s) {↵
size_t pos = s.find(':');↵
assert(pos != string::npos);↵
return make_pair(s.substr(0, pos), s.substr(pos + 1));↵
};↵
↵
auto splitIntoTokensOfLatinLetters = [](const string& s) {↵
vector<string> result;↵
string token;↵
for (char c : s) {↵
if (isalpha(c) || isdigit(c)) {↵
token += c;↵
}↵
else {↵
if (!token.empty()) {↵
result.push_back(token);↵
}↵
token.clear();↵
}↵
}↵
if (!token.empty()) {↵
result.push_back(token);↵
}↵
return result;↵
};↵
↵
int m;↵
cin >> m;↵
vector<int> who(m);↵
vector<vector<char>> can(m, vector<char>(n, true));↵
↵
vector<string> messages(m);↵
↵
string tmp;↵
getline(cin, tmp);↵
↵
for (int i = 0; i < m; i++) {↵
string cur;↵
getline(cin, cur);↵
pair<string, string> p = splitIntoUserMessage(cur);↵
const string& user = p.first;↵
const string& message = p.second;↵
who[i] = getIdx(user);↵
if (who[i] != -1) {↵
fill(all(can[i]), false);↵
can[i][who[i]] = true;↵
}↵
messages[i] = message;↵
vector<string> tokens = splitIntoTokensOfLatinLetters(message);↵
for (const string& z : tokens) {↵
int idx = getIdx(z);↵
if (idx != -1) {↵
can[i][idx] = false;↵
}↵
}↵
}↵
↵
vector<vector<int>> par(m, vector<int>(n, -1));↵
for (int i = 0; i < n; i++) {↵
if (can[0][i]) par[0][i] = 0;↵
}↵
for (int msg = 0; msg + 1 < m; msg++) {↵
for (int i = 0; i < n; i++) {↵
if (par[msg][i] == -1) continue;↵
for (int j = 0; j < n; j++) {↵
if (i == j) continue;↵
if (can[msg + 1][j]) {↵
par[msg + 1][j] = i;↵
}↵
}↵
}↵
}↵
int msg = m - 1, pos = -1;↵
for (int i = 0; i < n; i++) {↵
if (par[msg][i] != -1) {↵
pos = i;↵
break;↵
}↵
}↵
if (pos == -1) {↵
cout << "Impossible\n";↵
return;↵
}↵
while (msg >= 0) {↵
who[msg] = pos;↵
pos = par[msg][pos];↵
msg--;↵
}↵
for (int i = 0; i < m; i++) {↵
cout << names[who[i]] << ":" << messages[i] << "\n";↵
}↵
return;↵
}↵
↵
int main() {↵
//freopen("input.txt", "r", stdin);↵
int t;↵
cin >> t; // number of tests↵
↵
while (t--) {↵
solve();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[tutorial:754D]↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
typedef long long ll;↵
↵
int nextInt() {↵
int x = 0, p = 1;↵
char c;↵
do {↵
c = getchar();↵
} while (c <= 32);↵
if (c == '-') {↵
p = -1;↵
c = getchar();↵
}↵
while (c >= '0' && c <= '9') {↵
x = x * 10 + c - '0';↵
c = getchar();↵
}↵
return x * p;↵
}↵
↵
#define all(x) (x).begin(), (x).end()↵
↵
const int N = (int)3e5 + 5;↵
const int MAX_VAL = (int)1e9;↵
↵
int n;↵
ll l[N], r[N];↵
↵
struct event {↵
ll x;↵
int c;↵
event() {}↵
event(ll x, int c) : x(x), c(c) {}↵
};↵
↵
pair<ll, int> check(ll len) {↵
if (len == 0) return make_pair(0LL, n);↵
static vector<event> evs;↵
evs.resize(0);↵
for (int i = 1; i <= n; i++) {↵
if (r[i] - len > l[i]) {↵
evs.push_back(event(l[i], 1));↵
evs.push_back(event(r[i] - len, -1));↵
}↵
}↵
sort(all(evs), [](const event & a, const event & b) { return a.x < b.x; });↵
reverse(all(evs));↵
int cnt = 0, maxiCnt = 0;↵
ll bestPos = 0;↵
while (evs.size() > 0) {↵
ll x = evs.back().x;↵
while (evs.size() > 0 && evs.back().x == x) {↵
cnt += evs.back().c;↵
evs.pop_back();↵
}↵
if (cnt > maxiCnt) {↵
maxiCnt = cnt;↵
bestPos = x;↵
}↵
}↵
return make_pair(bestPos, maxiCnt);↵
}↵
↵
vector<int> getAns(ll len) {↵
if (len == 0) {↵
vector<int> res(n);↵
iota(all(res), 1);↵
return res;↵
}↵
ll pos = check(len).first;↵
vector<int> res;↵
for (int i = 1; i <= n; i++) {↵
if (pos >= l[i] && pos < r[i] - len) {↵
res.push_back(i);↵
}↵
}↵
return res;↵
}↵
↵
int main() {↵
n = nextInt();↵
int k = nextInt();↵
for (int i = 1; i <= n; i++) {↵
l[i] = nextInt();↵
r[i] = nextInt() + 2;↵
}↵
ll l = 0, r = MAX_VAL + MAX_VAL + 5;↵
while (r - l > 1) {↵
ll mid = (l + r) >> 1;↵
if (check(mid).second >= k) l = mid;↵
else r = mid;↵
}↵
↵
vector<int> ans = getAns(l);↵
↵
cout << l << endl;↵
assert((int)ans.size() >= k);↵
ans.resize(k);↵
for (int i : ans) {↵
printf("%d ", i);↵
}↵
puts("");↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:754E]↵
↵
<spoiler summary="C++ code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
const int N = (int)404;↵
const int ALPHA = 26;↵
↵
bitset<N> b[ALPHA][N];↵
char patt[N][N];↵
bitset<N> result[N];↵
↵
bitset<N> getShifted(const bitset<N>& b, int len, int shift) {↵
assert(0 <= shift && shift < len);↵
return (b >> shift) | (b << (len - shift));↵
}↵
↵
int main() {↵
#ifdef LOCAL↵
freopen("input.txt", "r", stdin);↵
#endif↵
int n, m, r, c;↵
scanf("%d%d", &n, &m);↵
↵
for (int i = 0; i < n; i++) {↵
static char str[N];↵
scanf("%s", str);↵
for (int j = 0; j < m; j++) {↵
b[(int)(str[j] - 'a')][i][j] = true;↵
}↵
}↵
↵
scanf("%d%d", &r, &c);↵
↵
for (int i = 0; i < n; i++) {↵
result[i] = ~result[i];↵
}↵
↵
for (int i = 0; i < r; i++) {↵
scanf("%s", patt[i]);↵
for (int j = 0; j < c; j++) {↵
if (patt[i][j] == '?') continue;↵
int c = patt[i][j] - 'a';↵
int shiftByX = (((-i) % n) + n) % n;↵
int shiftByY = (((j) % m) + m) % m;↵
for (int x = 0; x < n; x++) {↵
int nx = (x + shiftByX);↵
if (nx >= n) nx -= n;↵
result[nx] &= getShifted(b[c][x], m, shiftByY);↵
}↵
}↵
}↵
↵
for (int i = 0; i < n; i++) {↵
for (int j = 0; j < m; j++) {↵
putchar(result[i][j] ? '1' : '0');↵
}↵
puts("");↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Java code">↵
↵
~~~~~↵
import java.io.*;↵
import java.util.*;↵
↵
public class Main {↵
↵
static class InputReader {↵
BufferedReader bufferedReader;↵
StringTokenizer stringTokenizer;↵
InputReader(InputStream inputStream) {↵
bufferedReader = new BufferedReader(new InputStreamReader(inputStream), 32768);↵
stringTokenizer = null;↵
}↵
String next() {↵
while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {↵
try {↵
stringTokenizer = new StringTokenizer(bufferedReader.readLine());↵
} catch (IOException ex) {↵
ex.printStackTrace();↵
throw new RuntimeException(ex);↵
}↵
}↵
return stringTokenizer.nextToken();↵
}↵
int nextInt() {↵
return Integer.parseInt(next());↵
}↵
long nextLong() {↵
return Long.parseLong(next());↵
}↵
double nextDouble() {↵
return Double.parseDouble(next());↵
}↵
}↵
↵
static int[] newBitSet(int n) {↵
return new int[(n + 31) / 32];↵
}↵
↵
static void setBit(int[] a, int pos) {↵
a[pos >>> 5] |= (1 << (pos & 31));↵
}↵
↵
static boolean getBit(int[] a, int pos) {↵
return ((a[pos >>> 5]) & (1 << (pos & 31))) != 0;↵
}↵
↵
static void setAll(int[] a) {↵
for (int i = 0; i < a.length; i++) {↵
a[i] = ~0;↵
}↵
}↵
↵
static void resetAll(int[] a) {↵
for (int i = 0; i < a.length; i++) {↵
a[i] = 0;↵
}↵
}↵
↵
static void andXYtoX(int[] x, int[] y) {↵
for (int i = 0; i < x.length; i++) {↵
x[i] &= y[i];↵
}↵
}↵
↵
static void leftShiftAndOr(int ch, int shift, int x, int[][][][] shl, int[] to) {↵
int[] z = shl[ch][shift & 31][x];↵
int delta = (shift >>> 5);↵
for (int i = delta; i < to.length; i++) {↵
to[i - delta] |= z[i];↵
}↵
}↵
↵
static void rightShiftAndOr(int ch, int shift, int x, int[][][][] shr, int[] to) {↵
int[] z = shr[ch][shift & 31][x];↵
int delta = (shift >>> 5);↵
for (int i = 0; i + delta < to.length; i++) {↵
to[i + delta] |= z[i];↵
}↵
}↵
↵
static void printBitset(int a[], int l, int r) {↵
for (int i = l; i <= r; i++) {↵
System.err.print(getBit(a, i) ? '1' : '0');↵
}↵
System.err.println();↵
}↵
↵
static final int ALPHA = 26;↵
↵
public static void main(String[] args) {↵
InputReader in = new InputReader(System.in);↵
PrintWriter out = new PrintWriter(System.out);↵
↵
int n = in.nextInt();↵
int m = in.nextInt();↵
↵
int[][][][] shl = new int[ALPHA][32][n][];↵
int[][][][] shr = new int[ALPHA][32][n][];↵
↵
for (int c = 0; c < ALPHA; c++) {↵
for (int sh = 0; sh < 32; sh++) {↵
for (int i = 0; i < n; i++) {↵
shl[c][sh][i] = newBitSet(m);↵
shr[c][sh][i] = newBitSet(m);↵
}↵
}↵
}↵
↵
String[] s = new String[n];↵
↵
for (int i = 0; i < n; i++) {↵
s[i] = in.next();↵
for (int j = 0; j < m; j++) {↵
int c = s[i].charAt(j) - 'a';↵
for (int sh = 0; sh < 32; sh++) {↵
if (j - sh >= 0) {↵
setBit(shl[c][sh][i], j - sh);↵
}↵
if (j + sh < m) {↵
setBit(shr[c][sh][i], j + sh);↵
}↵
}↵
}↵
}↵
↵
int r = in.nextInt();↵
int c = in.nextInt();↵
↵
String[] patt = new String[r];↵
↵
int[][] res = new int[n][];↵
↵
for (int i = 0; i < n; i++) {↵
res[i] = newBitSet(m);↵
setAll(res[i]);↵
}↵
↵
int[] tmp = newBitSet(m);↵
↵
for (int i = 0; i < r; i++) {↵
patt[i] = in.next();↵
for (int j = 0; j < c; j++) {↵
if (patt[i].charAt(j) == '?') continue;↵
int cur = patt[i].charAt(j) - 'a';↵
int shiftByX = (((-i) % n) + n) % n;↵
int shiftByY = (((j) % m) + m) % m;↵
↵
for (int x = 0; x < n; x++) {↵
int nx = x + shiftByX;↵
if (nx >= n) nx -= n;↵
resetAll(tmp);↵
leftShiftAndOr(cur, shiftByY, x, shl, tmp);↵
rightShiftAndOr(cur, m - shiftByY, x, shr, tmp);↵
andXYtoX(res[nx], tmp);↵
}↵
}↵
}↵
↵
for (int i = 0; i < n; i++) {↵
for (int j = 0; j < m; j++) {↵
out.print(getBit(res[i], j) ? '1' : '0');↵
}↵
out.println();↵
}↵
↵
out.close();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
