#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="")

#include <bits/stdc++.h>
using namespace std;

vector<string> rd() {
    vector<string> v;
    string s;
    while (getline(cin, s)) v.push_back(s);
    return v;
}

tuple<int, vector<string>, vector<string>> ps() {
    auto d = rd();
    int i = 0;
    while (i < (int)d.size() && d[i].find_first_not_of(" \t\r") == string::npos) i++;
    if (i >= (int)d.size()) return {0, {}, {}};
    int n = stoi(d[i++]);
    while (i < (int)d.size() && d[i].find_first_not_of(" \t\r") == string::npos) i++;
    if (i < (int)d.size() && string(d[i].begin(), d[i].end()) == "shuffled") i++;
    vector<string> sh;
    for (int k = 0; k < n && i < (int)d.size(); k++) {
        while (i < (int)d.size() && d[i].empty()) i++;
        sh.push_back(d[i++]);
    }
    while (i < (int)d.size() && d[i].find_first_not_of(" \t\r") == string::npos) i++;
    if (i < (int)d.size() && string(d[i].begin(), d[i].end()) == "original") i++;
    vector<string> og;
    for (int k = 0; k < n && i < (int)d.size(); k++) {
        while (i < (int)d.size() && d[i].empty()) i++;
        og.push_back(d[i++]);
    }
    return {n, sh, og};
}

vector<int> mpv(const vector<string>& sh, const vector<string>& og) {
    unordered_map<string,int> m;
    for (int i = 0; i < (int)og.size(); i++) m[og[i]] = i + 1;
    vector<int> a;
    for (auto& s : sh) a.push_back(m[s]);
    return a;
}

vector<vector<int>> nb(const vector<int>& st) {
    int n = st.size();
    vector<vector<int>> res;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            vector<int> sg(st.begin() + i, st.begin() + j + 1);
            vector<int> rm;
            rm.insert(rm.end(), st.begin(), st.begin() + i);
            rm.insert(rm.end(), st.begin() + j + 1, st.end());
            for (int k = 0; k <= (int)rm.size(); k++) {
                if (k == i) continue;
                vector<int> y = rm;
                y.insert(y.begin() + k, sg.begin(), sg.end());
                res.push_back(y);
            }
        }
    }
    return res;
}

int bfs(vector<int> s, vector<int> t) {
    if (s == t) return 0;
    unordered_map<string,int> ds, dt;
    deque<vector<int>> qs, qt;
    auto to_str = [&](const vector<int>& v) {
        string r;
        for (int x : v) r += char('a' + x);
        return r;
    };
    qs.push_back(s);
    qt.push_back(t);
    ds[to_str(s)] = 0;
    dt[to_str(t)] = 0;
    while (!qs.empty() && !qt.empty()) {
        if (qs.size() <= qt.size()) {
            int m = qs.size();
            while (m--) {
                auto x = qs.front(); qs.pop_front();
                int dx = ds[to_str(x)];
                for (auto& y : nb(x)) {
                    string ky = to_str(y);
                    if (ds.count(ky)) continue;
                    ds[ky] = dx + 1;
                    if (dt.count(ky)) return ds[ky] + dt[ky];
                    qs.push_back(y);
                }
            }
        } else {
            int m = qt.size();
            while (m--) {
                auto x = qt.front(); qt.pop_front();
                int dx = dt[to_str(x)];
                for (auto& y : nb(x)) {
                    string ky = to_str(y);
                    if (dt.count(ky)) continue;
                    dt[ky] = dx + 1;
                    if (ds.count(ky)) return ds[ky] + dt[ky];
                    qt.push_back(y);
                }
            }
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    auto [n, sh, og] = ps();
    if (n == 0) {
        cout << 0;
        return 0;
    }
    auto s = mpv(sh, og);
    vector<int> t(n);
    iota(t.begin(), t.end(), 1);
    cout << bfs(s, t);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int a, b;
    bool operator==(const Node &o) const { return a == o.a && b == o.b; }
};
struct NodeHash {
    size_t operator()(const Node &p) const {
        return (uint64_t(uint32_t(p.a)) << 32) ^ uint32_t(p.b);
    }
};
struct State {
    int a, b, id;
    bool operator==(const State &o) const { return a == o.a && b == o.b && id == o.id; }
};
struct StateHash {
    size_t operator()(const State &k) const {
        uint64_t val = k.a;
        val = (val << 20) ^ k.b;
        val = (val << 20) ^ k.id;
        return size_t(val);
    }
};

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

    vector<long long> in;
    long long t;
    while (cin >> t) in.push_back(t);

    int idx = 0, n = (int)in[idx++];
    vector<array<int, 4>> seg(n);
    for (int i = 0; i < n; i++) {
        seg[i][0] = (int)in[idx++];
        seg[i][1] = (int)in[idx++];
        seg[i][2] = (int)in[idx++];
        seg[i][3] = (int)in[idx++];
    }

    int sx = (int)in[idx++], sy = (int)in[idx++], energy = (int)in[idx++];

    unordered_map<Node, vector<int>, NodeHash> grid;
    unordered_map<State, pair<int, int>, StateHash> moveNext;

    for (int id = 0; id < n; id++) {
        int x1 = seg[id][0], y1 = seg[id][1];
        int x2 = seg[id][2], y2 = seg[id][3];
        int dx = (x2 > x1) ? 1 : -1;
        int dy = (y2 > y1) ? 1 : -1;
        int len = abs(x2 - x1);

        if (dy == -1) {
            for (int s = 0; s < len; s++) {
                int nx = x1 + dx * s;
                int ny = y1 - s;
                grid[{nx, ny}].push_back(id);
                moveNext[{nx, ny, id}] = {nx + dx, ny - 1};
            }
            grid[{x2, y2}].push_back(id);
        } else {
            for (int s = 0; s < len; s++) {
                int nx = x2 - dx * s;
                int ny = y2 - s;
                grid[{nx, ny}].push_back(id);
                moveNext[{nx, ny, id}] = {nx - dx, ny - 1};
            }
            grid[{x1, y1}].push_back(id);
        }
    }

    auto fall = [&](int cx, int cy) -> pair<int, int> {
        for (int yy = cy - 1; yy >= 0; yy--) {
            if (grid.count({cx, yy})) return {cx, yy};
        }
        return {cx, 0};
    };

    int x = sx, y = sy;
    if (!grid.count({x, y})) tie(x, y) = fall(x, y);

    while (true) {
        if (y == 0) break;

        auto it = grid.find({x, y});
        if (it == grid.end()) {
            tie(x, y) = fall(x, y);
            continue;
        }

        auto &ids = it->second;
        if (ids.size() == 1) {
            int sid = ids[0];
            auto nxt = moveNext.find({x, y, sid});
            if (nxt == moveNext.end()) {
                tie(x, y) = fall(x, y);
                continue;
            }
            if (energy == 0) break;
            energy--;
            x = nxt->second.first;
            y = nxt->second.second;
        } else {
            long long cost = 1LL * x * y;
            vector<pair<int, pair<int, int>>> nxtList;
            for (int sid : ids) {
                auto it2 = moveNext.find({x, y, sid});
                if (it2 != moveNext.end()) nxtList.push_back({sid, it2->second});
            }

            if (energy <= cost) {
                if (nxtList.empty()) {
                    tie(x, y) = fall(x, y);
                    continue;
                }
                break;
            }

            energy -= (int)cost;
            if (nxtList.empty()) {
                tie(x, y) = fall(x, y);
                continue;
            }

            int bx = 0, by = -1;
            for (auto &it3 : nxtList) {
                if (it3.second.second > by) {
                    by = it3.second.second;
                    bx = it3.second.first;
                }
            }
            if (energy == 0) break;
            energy--;
            x = bx;
            y = by;
        }
    }

    cout << x << " " << y;
    return 0;
}

import sys, heapq

def read_input():
    lines = [l.strip() for l in sys.stdin if l.strip()]
    n = int(lines[0])
    shuffled = lines[2:2+n]
    original = lines[3+n:]
    return n, shuffled, original

def make_perm(shuffled, original):
    idx = {v: i for i, v in enumerate(original)}
    return tuple(idx[x] for x in shuffled)

def neighbors(state):
    n = len(state)
    for i in range(n):
        for j in range(i, n):
            seg = state[i:j+1]
            rem = state[:i] + state[j+1:]
            for k in range(len(rem)+1):
                if k == i:
                    continue
                yield rem[:k] + seg + rem[k:]

def heuristic(state):
    h = 0
    for i in range(len(state)-1):
        if abs(state[i+1]-state[i]) != 1:
            h += 1
    return h

def astar(start, goal):
    pq = [(heuristic(start), 0, start)]
    dist = {start: 0}
    while pq:
        f, g, cur = heapq.heappop(pq)
        if cur == goal:
            return g
        for nxt in neighbors(cur):
            ng = g + 1
            if nxt not in dist or ng < dist[nxt]:
                dist[nxt] = ng
                heapq.heappush(pq, (ng + heuristic(nxt), ng, nxt))
    return -1

def main():
    n, shuffled, original = read_input()
    if n == 0:
        print(0, end="")
        return
    start = make_perm(shuffled, original)
    goal = tuple(range(n))
    print(astar(start, goal), end="")

main()