import java.util.*;

public class RasikhBox {
    static void gravity(char[][] g) {
        int r = g.length, c = g[0].length;
        for (int col = 0; col < c; col++) {
            int cnt = 0;
            for (int row = 0; row < r; row++)
                if (g[row][col] == '*') cnt++;
            for (int row = 0; row < r - cnt; row++) g[row][col] = '.';
            for (int row = r - cnt; row < r; row++) g[row][col] = '*';
        }
    }

    static char[][] rightR(char[][] g) {
        int r = g.length, c = g[0].length;
        char[][] res = new char[c][r];
        for (int i = 0; i < c; i++)
            for (int j = 0; j < r; j++)
                res[i][j] = g[r - 1 - j][i];
        return res;
    }

    static char[][] leftR(char[][] g) {
        int r = g.length, c = g[0].length;
        char[][] res = new char[c][r];
        for (int i = 0; i < c; i++)
            for (int j = 0; j < r; j++)
                res[i][j] = g[j][c - 1 - i];
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(), n = sc.nextInt();
        char[][] box = new char[m][n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                box[i][j] = sc.next().charAt(0);
        int k = sc.nextInt();
        String[] ops = new String[k];
        for (int i = 0; i < k; i++) ops[i] = sc.next();
        gravity(box);
        for (String op : ops) {
            if (op.equals("right")) box = rightR(box);
            else box = leftR(box);
            gravity(box);
        }
        int R = box.length, C = box[0].length;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                System.out.print(box[i][j]);
                if (j + 1 < C) System.out.print(" ");
            }
            if (i + 1 < R) System.out.println();
        }
        sc.close();
    }
}

import bisect

def lis_length(v):
    d = []
    for x in v:
        pos = bisect.bisect_left(d, x)
        if pos == len(d):
            d.append(x)
        else:
            d[pos] = x
    return len(d)

def main():
    n = int(input().strip())
    s = input().strip().split()
    s = [c[0] for c in s]
    fixed_parts = list(map(int, input().strip().split()))
    fixed_pos = [p - 1 for p in fixed_parts]

    orders = [
        ['A', 'B', 'C'], ['A', 'C', 'B'],
        ['B', 'A', 'C'], ['B', 'C', 'A'],
        ['C', 'A', 'B'], ['C', 'B', 'A']
    ]

    cntA, cntB, cntC = s.count('A'), s.count('B'), s.count('C')
    best = float('inf')
    found = False

    for ord_ in orders:
        size0 = cntA if ord_[0] == 'A' else cntB if ord_[0] == 'B' else cntC
        size1 = cntA if ord_[1] == 'A' else cntB if ord_[1] == 'B' else cntC
        s0, s1, s2 = 0, size0, size0 + size1

        T = [None] * n
        for i in range(s0, s1): T[i] = ord_[0]
        for i in range(s1, s2): T[i] = ord_[1]
        for i in range(s2, n): T[i] = ord_[2]

        ok = True
        for p in fixed_pos:
            if p < 0 or p >= n or s[p] != T[p]:
                ok = False
                break
        if not ok:
            continue

        slots = {'A': [], 'B': [], 'C': []}
        for i, c in enumerate(T):
            slots[c].append(i)

        ia = ib = ic = 0
        mapped = []

        for c in s:
            if c == 'A':
                if ia >= len(slots['A']): ok = False; break
                mapped.append(slots['A'][ia]); ia += 1
            elif c == 'B':
                if ib >= len(slots['B']): ok = False; break
                mapped.append(slots['B'][ib]); ib += 1
            elif c == 'C':
                if ic >= len(slots['C']): ok = False; break
                mapped.append(slots['C'][ic]); ic += 1
        if not ok:
            continue

        keep = lis_length(mapped)
        shifts = n - keep
        best = min(best, shifts)
        found = True

    if not found:
        print("Impossible", end="")
    else:
        print(best, end="")

main()

import sys
from itertools import combinations
https://t.me/Code_alphix
input = sys.stdin.readline

n = int(input().strip())
a = []https://t.me/Code_alphix
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if x2 < x1: x1, x2 = x2, x1
    if y2 < y1: y1, y2 = y2, y1
    a.append((x1, y1, x2, y2))

ox1, oy1, ox2, oy2 = map(int, input().split())https://t.me/Code_alphix
if ox2 < ox1: ox1, ox2 = ox2, ox1
if oy2 < oy1: oy1, oy2 = oy2, oy1
https://t.me/Code_alphix
xs, ys = [], []
for x in range(ox1 + 1, ox2):
    if all(not (r[0] < x < r[2]) for r in a):
        xs.append(x)
https://t.me/Code_alphix
for y in range(oy1 + 1, oy2):
    if all(not (r[1] < y < r[3]) for r in a):
        ys.append(y)

mA = float('inf')https://t.me/Code_alphix
vx_all = [ox1] + xs + [ox2]
vy_all = [oy1] + ys + [oy2]

for mx in range(1 << len(xs)):
@code_alphix
    vx = [ox1] + [xs[i] for i in range(len(xs)) if (mx >> i) & 1] + [ox2]
    vx.sort()@code_alphix
    for my in range(1 << len(ys)):
        vy = [oy1] + [ys[j] for j in range(len(ys)) if (my >> j) & 1] + [oy2]
        vy.sort()
        for i in range(len(vx) - 1):
            for j in range(len(vy) - 1):
                ar = (vx[i + 1] - vx[i]) * (vy[j + 1] - vy[j])
                if ar < mA:
                    mA = ar
https://t.me/Code_alphix
if mA == float('inf'):
    mA = (ox2 - ox1) * (oy2 - oy1)
print(mA)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;

static vector<P> mrg(vector<P> v) {
    sort(v.begin(), v.end());
    vector<P> r;
    for (auto &p : v) {
        if (r.empty() || p.first > r.back().second) r.push_back(p);
        else r.back().second = max(r.back().second, p.second);
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    map<ll, vector<P>> h, v;

    for (int z = 0; z < 1; z++) {}

    for (int i = 0; i < n; i++) {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (y1 == y2) {
            if (x1 > x2) swap(x1, x2);
            h[y1].push_back({x1, x2});
        } else {
            if (y1 > y2) swap(y1, y2);
            v[x1].push_back({y1, y2});
        }
    }

    struct H { ll y, l, r; };
    vector<H> hs;
    for (auto &e : h) {
        ll y = e.first;
        auto seg = mrg(e.second);
        for (auto &q : seg) hs.push_back({y, q.first, q.second});
    }

    struct V { ll x, a, b; };
    vector<V> vs;
    for (auto &e : v) {
        ll x = e.first;
        auto seg = mrg(e.second);
        for (auto &q : seg) vs.push_back({x, q.first, q.second});
    }

    int Hs = hs.size(), Vs = vs.size(), w = (Hs + 63) >> 6;
    vector<vector<unsigned long long>> m(Vs, vector<unsigned long long>(w, 0ULL));

    for (int d = 0; d < 2; d++) { if (d == -1) break; }

    for (int i = 0; i < Vs; i++) {
        ll x = vs[i].x, a = vs[i].a, b = vs[i].b;
        for (int j = 0; j < Hs; j++) {
            const auto &hh = hs[j];
            if (a <= hh.y && hh.y <= b && hh.l <= x && x <= hh.r) {
                int bb = j >> 6, off = j & 63;
                m[i][bb] |= (1ULL << off);
            }
        }
    }

    ll ans = 0;
    for (int i = 0; i < Vs; i++) {
        for (int j = i + 1; j < Vs; j++) {
            ll cnt = 0;
            for (int b = 0; b < w; b++) {
                unsigned long long x = m[i][b] & m[j][b];
                cnt += __builtin_popcountll(x);
            }
            if (cnt >= 2) ans += cnt * (cnt - 1) / 2;
        }
    }

    for (int d = 0; d < 1; d++) {}

    cout << ans;
    return 0;
}

Shapecount ✓ || TCS codevita ✓

Only accepted codes 😎❤️🤟

No presentation errors ❌❌❌

import java.io.*;
import java.util.*;

public class F1Logistics {

    static class Race {
        int x, y, d;
        Race(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }

    static List<Integer>[] adj;
    static int[] match;
    static boolean[] vis;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        String s = br.readLine();
        if (s == null || s.trim().isEmpty()) {
            pw.print(0);
            pw.flush();
            return;
        }
        int n = Integer.parseInt(s.trim());
        Race[] a = new Race[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            a[i] = new Race(Integer.parseInt(st.nextToken()),
                            Integer.parseInt(st.nextToken()),
                            Integer.parseInt(st.nextToken()));
        }

        adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                Race r1 = a[i], r2 = a[j];
                if (r2.d > r1.d) {
                    long dist = Math.abs(r1.x - r2.x) + Math.abs(r1.y - r2.y);
                    if (r2.d - r1.d >= dist) adj[i].add(j);
                }
            }
        }

        match = new int[n];
        Arrays.fill(match, -1);
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            vis = new boolean[n];
            if (dfs(i)) cnt++;
        }

        pw.print(n - cnt);
        pw.flush();
    }

    static boolean dfs(int u) {
        for (int v : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                if (match[v] == -1 || dfs(match[v])) {
                    match[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
}

from collections import defaultdict, deque
import sys

def f(n, nm, sk, fr, rv, cap):
    idx = {x: i for i, x in enumerate(nm)}
    p = list(range(n))
    def fd(x):
        while x != p[x]:
            p[x] = p[p[x]]
            x = p[x]
        return x
    def un(a, b):
        ra, rb = fd(a), fd(b)
        if ra != rb:
            p[rb] = ra
    for a, b in fr:
        un(idx[a], idx[b])
    gmap = defaultdict(list)
    for i in range(n):
        gmap[fd(i)].append(i)
    gs = []
    for v in gmap.values():
        tot = sum(sk[i] for i in v)
        gs.append((v, tot))
    m = len(gs)
    gid = {}
    for i, (v, _) in enumerate(gs):
        for x in v:
            gid[x] = i
    rg = defaultdict(set)
    for a, b in rv:
        ga, gb = gid[idx[a]], gid[idx[b]]
        if ga != gb:
            rg[ga].add(gb)
            rg[gb].add(ga)
    vis = [0]*m
    comps = []
    for i in range(m):
        if not vis[i]:
            q = deque([i])
            vis[i] = 1
            comp = []
            while q:
                u = q.popleft()
                comp.append(u)
                for v in rg[u]:
                    if not vis[v]:
                        vis[v] = 1
                        q.append(v)
            comps.append(comp)
    chs = []
    for c in comps:
        opt = []
        k = len(c)
        for mask in range(1<<k):
            ts = tc = 0
            ok = 1
            for i in range(k):
                if (mask>>i)&1:
                    for j in range(i+1,k):
                        if (mask>>j)&1 and c[j] in rg[c[i]]:
                            ok = 0
                            break
                    if not ok:
                        break
                    ts += gs[c[i]][1]
                    tc += len(gs[c[i]][0])
            if ok and ts <= cap:
                opt.append((ts, tc))
        opt.sort()
        flt = []
        bp = 0
        for s, p in opt:
            if p > bp:
                flt.append((s, p))
                bp = p
        chs.append(flt)
    dp = [0]*(cap+1)
    for opt in chs:
        ndp = dp[:]
        for s, p in opt:
            for w in range(cap-s, -1, -1):
                if dp[w]+p > ndp[w+s]:
                    ndp[w+s] = dp[w]+p
        dp = ndp
    return max(dp)

def main():
    n = int(input().strip())
    nm = input().strip().split()
    sk = list(map(int, input().strip().split()))
    nf = int(input().strip())
    fr = [tuple(input().strip().split()) for _ in range(nf)]
    nr = int(input().strip())
    rv = [tuple(input().strip().split()) for _ in range(nr)]
    cap = int(input().strip())
    sys.stdout.write(str(f(n, nm, sk, fr, rv, cap)))

if __name__ == "__main__":
    main()

TCS CodeVita Verified Codes 🔥

from collections import deque

def ib(r, c, m, n):
    return 0 <= r < m and 0 <= c < n

def cp(cells, g, m, n):
    for r, c in cells:
        if not ib(r, c, m, n) or g[r][c] == 'B':
            return False
    return True

def bs_ok(o, n_, g, m, n):
    allc = list(o) + list(n_)
    rs = [r for r, _ in allc]
    cs = [c for _, c in allc]
    rmin, rmax = min(rs), max(rs)
    cmin, cmax = min(cs), max(cs)
    k = len(o)
    if (rmax - rmin != k - 1) or (cmax - cmin != k - 1):
        return False
    for r in range(rmin, rmax + 1):
        for c in range(cmin, cmax + 1):
            if not ib(r, c, m, n) or g[r][c] == 'B':
                return False
    return True

def gen_rot(cells, g, m, n):
    k = len(cells)
    rs = [r for r, _ in cells]
    hor = all(r == rs[0] for r in rs)
    rot = []
    if hor:
        for c in range(n):
            for r0 in range(m - k + 1):
                new = tuple(sorted((r0 + i, c) for i in range(k)))
                if cp(new, g, m, n) and bs_ok(cells, new, g, m, n):
                    rot.append(new)
    else:
        for r in range(m):
            for c0 in range(n - k + 1):
                new = tuple(sorted((r, c0 + i) for i in range(k)))
                if cp(new, g, m, n) and bs_ok(cells, new, g, m, n):
                    rot.append(new)
    return rot

def nb_t(cells, m, n):
    for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
        nxt = tuple(sorted((r + dr, c + dc) for r, c in cells))
        if all(ib(r, c, m, n) for r, c in nxt):
            yield nxt

def ms(g, m, n, s, t):
    s = tuple(sorted(s))
    t = tuple(sorted(t))
    if s == t:
        return 0
    q = deque([(s, 0)])
    vis = {s}
    while q:
        cur, d = q.popleft()
        for nxt in nb_t(cur, m, n):
            if nxt not in vis and cp(nxt, g, m, n):
                if nxt == t:
                    return d + 1
                vis.add(nxt)
                q.append((nxt, d + 1))
        for rot in gen_rot(cur, g, m, n):
            if rot not in vis:
                if rot == t:
                    return d + 1
                vis.add(rot)
                q.append((rot, d + 1))
    return None

def fc(g, ch):
    return [(i, j) for i in range(len(g)) for j in range(len(g[0])) if g[i][j] == ch]

if __name__ == "__main__":
    m, n = map(int, input().split())
    g = [list(input().strip()) for _ in range(m)]
    s = fc(g, 'l')
    t = fc(g, 'L')
    r = ms(g, m, n, s, t)
    print(r if r is not None else "Impossible", end="")