Разбор раундаEditorial. Codeforces Round #390 (Div. 2)
Difference between ru1 and en1, changed 12,560 character(s)
[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>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian netman 2017-01-07 19:01:58 1
en1 English netman 2017-01-07 19:00:20 12560 Initial revision for English translation
ru1 Russian netman 2017-01-07 18:59:29 12562 Первая редакция (опубликовано)