AtCoder Regular Contest 074: F - Lotus Leaves

,

http://arc074.contest.atcoder.jp/tasks/arc074_d

無向グラフに流すときって単に両向きに張るだけでいいんだっけ?コストは両方同じ$1$でいいのか?とか言ってた。

solution

行と列を頂点、蓮の葉を辺として無向グラフを作り、最小カットを求める。 Ford-Fulkerson法で$E \le HW$かつ$F \le H + W$なので$O(HW (H + W))$。

implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

struct edge_t { int to, cap, rev; };
int maximum_flow_destructive(int s, int t, vector<vector<edge_t> > & g) { // ford fulkerson, O(EF)
    int n = g.size();
    vector<bool> used(n);
    function<int (int, int)> dfs = [&](int i, int f) {
        if (i == t) return f;
        used[i] = true;
        for (edge_t & e : g[i]) {
            if (used[e.to] or e.cap <= 0) continue;
            int nf = dfs(e.to, min(f, e.cap));
            if (nf > 0) {
                e.cap -= nf;
                g[e.to][e.rev].cap += nf;
                return nf;
            }
        }
        return 0;
    };
    int result = 0;
    while (true) {
        used.clear(); used.resize(n);
        int f = dfs(s, numeric_limits<int>::max());
        if (f == 0) break;
        result += f;
    }
    return result;
}
void add_edge(vector<vector<edge_t> > & g, int from, int to, int cap) {
    g[from].push_back((edge_t) {   to, cap, int(g[  to].size()    ) });
    g[  to].push_back((edge_t) { from,   0, int(g[from].size() - 1) });
}

int main() {
    // input
    int h, w; scanf("%d%d", &h, &w);
    int inf = h*w;
    vector<vector<char> > f = vectors(h, w, char());
    repeat (y,h) repeat (x,w) scanf(" %c", &f[y][x]);
    // maximum flow
    const int src = 0;
    const int dst = 1;
    auto node_y = [&](int y) { return 2 + y; };
    auto node_x = [&](int x) { return 2 + h + x; };
    vector<vector<edge_t> > g(2 + h + w);
    repeat (y,h) repeat (x,w) {
        if (f[y][x] == 'S') {
            add_edge(g, src, node_y(y), inf);
            add_edge(g, src, node_x(x), inf);
        } else if (f[y][x] == 'T') {
            add_edge(g, node_y(y), dst, inf);
            add_edge(g, node_x(x), dst, inf);
        }
        if (f[y][x] != '.') {
            add_edge(g, node_y(y), node_x(x), 1);
            add_edge(g, node_x(x), node_y(y), 1);
        }
    }
    int flow = maximum_flow_destructive(src, dst, g);
    // output
    if (flow >= inf) flow = -1;
    printf("%d\n", flow);
    return 0;
}

AtCoder Regular Contest 074: E - RGB Sequence

,

http://arc074.contest.atcoder.jp/tasks/arc074_c

overflowでたくさんWAを生やした。 clangかつ-fsanitize=undefinedだとbitsetstd::hashの周りでコンパイルこけるのが悪い、と思ったけど問題となるテストケース作ってなかったのでいずれにせよだめ。

solution

unordered_map<bitset<3*MAX_N>, int>な動的計画法。計算量解析は難しいが、自明な上界は$O(N 3^M)$。非想定っぽい。

各クエリがその区間中にどの色を持っているかをbitset<3*MAX_N>で表し、これの上で状態遷移させる。 無効な状態は積極的に消去し、また不要になったクエリの情報は全て塗り潰して状態をまとめる。 これらをきちんとやれば間に合う。

implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#include <bitset>
#include <tuple>
#include <unordered_map>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;

constexpr int mod = 1e9+7;
constexpr int MAX_M = 300;
int main() {
    // input
    int n, m; scanf("%d%d", &n, &m);
    vector<int> l(m), r(m), x(m); repeat (i,m) { scanf("%d%d%d", &l[i], &r[i], &x[i]); -- l[i]; } // [l, r)
    assert (m <= MAX_M);
    // dp
    unordered_map<bitset<3*MAX_M>, int> cur;
    unordered_map<bitset<3*MAX_M>, int> prv;
    cur[bitset<3*MAX_M>()] += 1;
    vector<int> queries;
    repeat (i,n) {
        cur.swap(prv);
        cur.clear();
        repeat (j,m) if (l[j] == i) {
            queries.push_back(j);
        }
        whole(sort, queries);
        repeat (c,3) { // RGB
            for (auto && it : prv) {
                bitset<3*MAX_M> s; int cnt; tie(s, cnt) = it;
                for (int j : queries) {
                    s[3*j+c] = true;
                    if (s[3*j+0] + s[3*j+1] + s[3*j+2] > x[j]) {
                        cnt = 0;
                        break;
                    }
                }
                if (cnt) {
                    cur[s] += cnt;
                    cur[s] %= mod;
                }
            }
        }
        cur.swap(prv);
        cur.clear();
        for (auto && it : prv) {
            bitset<3*MAX_M> s; int cnt; tie(s, cnt) = it;
            for (int j : queries) if (r[j]-1 == i) {
                if (s[3*j+0] + s[3*j+1] + s[3*j+2] != x[j]) {
                    cnt = 0;
                    break;
                }
                s[3*j+0] = false;
                s[3*j+1] = false;
                s[3*j+2] = false;
            }
            if (cnt) {
                cur[s] += cnt;
                cur[s] %= mod;
            }
        }
        repeat (j,m) if (r[j]-1 == i) {
            queries.erase(whole(remove, queries, j), queries.end());
        }
    }
    assert (queries.size() == 0);
    ll result = 0;
    for (auto && it : cur) {
        result += it.second;
    }
    result %= mod;
    // output
    printf("%lld\n", result);
    return 0;
}

AtCoder Regular Contest 074: D - 3N Numbers

,

http://arc074.contest.atcoder.jp/tasks/arc074_b

solution

$[0, r)$から$N$個選んだときの最大値と$[l, 3N)$から$N$個選んだときの最小値をそれぞれ$O(N \log N)$で計算しておいてまとめる。$O(N \log N)$。

$N$個選んだときの最大値最小値には、要素数が$N$という不変条件を持たせてpriority_queueとかを使う。

implementation

#include <cstdio>
#include <vector>
#include <queue>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
using ll = long long;
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;

constexpr ll inf = ll(1e18)+9;
int main() {
    // input
    int n; scanf("%d", &n);
    vector<ll> a(3*n); repeat (i,3*n) scanf("%lld", &a[i]);
    // compute
    vector<ll> front(3*n+1); {
        reversed_priority_queue<ll> que;
        repeat (i,3*n) {
            que.push(a[i]);
            ll b = 0;
            if (que.size() == n+1) {
                b = que.top(); que.pop();
            }
            front[i+1] = front[i] + a[i] - b;
        }
    }
    vector<ll> back(3*n+1); {
        priority_queue<ll> que;
        repeat_reverse (i,3*n) {
            que.push(a[i]);
            ll b = 0;
            if (que.size() == n+1) {
                b = que.top(); que.pop();
            }
            back[i] = back[i+1] + a[i] - b;
        }
    }
    ll result = - inf;
    repeat_from (i,n,2*n+1) {
        setmax(result, front[i] - back[i]);
    }
    // output
    printf("%lld\n", result);
    return 0;
}

AtCoder Regular Contest 074: C - Chocolate Bar

,

http://arc074.contest.atcoder.jp/tasks/arc074_a

チャレンジ失敗をした。

solution

分け方は 大きく分けて $4$通り。$O(H + W)$。

$3$分割する場合はちょうどやり、$2$分割を$2$回する場合は最初の分割を総当たりし次は真ん中で。

図:

+----+-----+-----+
|    |     |     |
|    |     |     |
|    |     |     |
|    |     |     |
|    |     |     |
+----+-----+-----+
+----+-----------+
|    |           |
|    |           |
|    +-----------+
|    |           |
|    |           |
+----+-----------+

implementation

#include <cstdio>
#include <algorithm>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i))
using ll = long long;
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

constexpr ll inf = ll(1e18)+9;
int main() {
    // input
    ll h, w; scanf("%lld%lld", &h, &w);
    auto maxdiff = [&](ll ah, ll aw, ll bh, ll bw, ll ch, ll cw) {
        assert (0 <= ah and ah <= h);
        assert (0 <= bh and bh <= h);
        assert (0 <= ch and ch <= h);
        assert (0 <= aw and aw <= w);
        assert (0 <= bw and bw <= w);
        assert (0 <= cw and cw <= w);
        ll as = ah * aw;
        ll bs = bh * bw;
        ll cs = ch * cw;
        assert (as + bs + cs == h * w);
        return max(abs(as - bs), max(abs(bs - cs), abs(cs - as)));
    };
    // solve
    ll result = inf;
    { // // hr, hr
        ll ah = h / 3;
        ll bh = (h - ah) / 2;
        ll ch = h - ah - bh;
        setmin(result, maxdiff(ah, w, bh, w, ch, w));
    }
    { // // vr, vr
        ll aw = w / 3;
        ll bw = (w - aw) / 2;
        ll cw = w - aw - bw;
        setmin(result, maxdiff(h, aw, h, bw, h, cw));
    }
    { // // vr, hr
        ll ah = h;
        repeat_from (aw,0,w+1) {
            ll bw = w - aw;
            ll cw = w - aw;
            ll bh = h / 2;
            ll ch = h - bh;
            setmin(result, maxdiff(ah, aw, bh, bw, ch, cw));
        }
    }
    { // // hr, vr
        ll aw = w;
        repeat_from (ah,0,h+1) {
            ll bh = h - ah;
            ll ch = h - ah;
            ll bw = w / 2;
            ll cw = w - bw;
            setmin(result, maxdiff(ah, aw, bh, bw, ch, cw));
        }
    }
    // output
    printf("%lld\n", result);
    return 0;
}

オンラインジャッジサーバ上でstd::threadを使う

,

背景

オンラインジャッジサービス上ではコンパイルオプションを自由に変更できない場合がある。 最適化オプションやライブラリの有無として頻繁に問題になる。 この問題の解決策のひとつとして __libc_dlopen_mode builtin関数などを使って実行時に陽に動的リンクすることが知られている。

しかしstd::threadの利用の際にlibpthreadをリンクするのには注意が必要であったので書いておく。

weak symbol

ELF formatの機能としてweak symbolがある。 strongな(つまり通常の)symbolが定義されなかった場合にdefaultとして用いられるsymbolのことである。

std::thread(とそれを所持するlibstdc++)はこの機能を用いて、std::threadが実際に使われない限りlibpthreadをリンクしなくてもよいようにしている。 これがなければC++のプログラムは常にlibpthreadをリンクしなければならなくなってしまう。

これはreadelfで確認すると以下のようにWEAKとなっている。

$ readelf -s /usr/lib/x86_64-linux-gnu/libstdc++.so.6
Symbol table '.dynsym' contains 5526 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
...
    80: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND pthread_create
...

これだけであれば単にダミーのsymbolを置いてリンクを通してしまえばよい。 しかし実装によってはリンク状況を確認する機能が存在する。 つまりリンカはpthread_createだけを要求したとしても、実行時に他の関数がリンクされていることを確認しだめなら以下のように例外を吐く。

terminate called after throwing an instance of 'std::system_error'
  what():  Enable multithreading to use std::thread: Operation not permitted

これは単に(リンカが要求した以外に)暗黙に要求されているシンボルを定義してやることで解決できる。

実装例

#include <cstdio>
#include <thread>
#include <cassert>
using ll = long long;
using namespace std;

extern "C" {
void *__libc_dlopen_mode(const char *x, int y);
void *__libc_dlsym(void *x, const char *y);
}
struct dynamic_library {
    void *handle;
    dynamic_library(string const & path) {
        int rtld_now = 2;
        handle = __libc_dlopen_mode(path.c_str(), rtld_now);
    }
    void *operator () (string const & symbol) {
        return __libc_dlsym(handle, symbol.c_str());
    }
};

const char *pthread_path = "/lib/x86_64-linux-gnu/libpthread.so.0"; // atcoder
// const char *pthread_path = "/usr/lib64/libpthread.so.0"; // yukicoder
dynamic_library pthread_handle(pthread_path);
extern "C" {
int pthread_create (pthread_t *__restrict __newthread,
        const pthread_attr_t *__restrict __attr,
        void *(*__start_routine) (void *),
        void *__restrict __arg) {
    typedef decltype(pthread_create) (*type);
    static type ptr = (type)(pthread_handle("pthread_create"));
    return ptr(__newthread, __attr, __start_routine, __arg);
}
void pthread_exit (void *__retval) {
    typedef decltype(pthread_exit) (*type);
    static type ptr = (type)(pthread_handle("pthread_exit"));
    ptr(__retval);
}
int pthread_join (pthread_t __th, void **__thread_return) {
    typedef decltype(pthread_join) (*type);
    static type ptr = (type)(pthread_handle("pthread_join"));
    return ptr(__th, __thread_return);
}
int pthread_detach (pthread_t __th) {
    typedef decltype(pthread_detach) (*type);
    static type ptr = (type)(pthread_handle("pthread_detach"));
    return ptr(__th);
}
}

constexpr int mod = 1e9+7;
void func(int l, int r, int *result) {
    ll acc = 1;
    for (int i = l; i < r; ++ i) {
        acc = acc * i % mod;
    }
    *result = acc;
}
int main() {
    int n = 1000000005;
    int result[4];
    constexpr int num_threads = 4;
    thread th[num_threads];
    for (int i = 0; i < num_threads; ++ i) {
        int l = (n - 1) *(ll)  i    / num_threads + 1;
        int r = (n - 1) *(ll) (i+1) / num_threads + 1;
        th[i] = thread(func, l, r, &result[i]);
    }
    ll acc = 1;
    for (int i = 0; i < num_threads; ++ i) {
        th[i].join();
        acc = acc * result[i] % mod;
    }
    assert (acc == 500000003);
    return 0;
}

Google Code Jam 2017 Round 2: B. Roller Coaster Scheduling

,

https://code.google.com/codejam/contest/5314486/dashboard#s=p1

本番はflowを流してSmallだけ。 Largeは後から解いたが、Contest Analysis読んでも分からなかったのでなんとなくで書いたら通った。 正確には、読んでも分からないのでなくて英語が長くてつらいので丁寧に読むのが面倒。 未証明。

solution

それらしい下限を求めたらそれが答え。$O(N + C + M)$。

各客について、客の持つチケットの枚数は下限。 各位置について、その位置を$p$ ($1 \le p \le N$)として$p$より前のチケットの総数$S$に対し$\frac{S}{p} \in \mathbb{Q}$は下限。 この下限が答え。

promotionの回数について。 上で求めた運行の回数を$R$とする。 各位置についてのその位置のをチケットの総数$S$に対し$\max(0, S - R)$を考え、その総和が回数。

implementation

#include <cstdio>
#include <vector>
#include <tuple>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }

pair<int, int> solve(int n, int c, int m, vector<int> const & p, vector<int> const & b) {
    vector<int> p_cnt(n);
    vector<int> b_cnt(c);
    repeat (i,m) {
        p_cnt[p[i]] += 1;
        b_cnt[b[i]] += 1;
    }
    int rides = 0;
    repeat (i,c) {
        setmax(rides, b_cnt[i]);
    }
    int p_acc = 0;
    repeat (i,n) {
        p_acc += p_cnt[i];
        setmax(rides, (p_acc + (i+1)-1) / (i+1));
    }
    int tickets = 0;
    repeat (i,n) {
        tickets += max(0, p_cnt[i] - rides);
    }
    return { rides, tickets };
}

int main() {
    int t; scanf("%d", &t);
    repeat (x,t) {
        int n, c, m; scanf("%d%d%d", &n, &c, &m);
        vector<int> p(m), b(m); repeat (i,m) { scanf("%d%d", &p[i], &b[i]); -- p[i]; -- b[i]; }
        int y, z; tie(y, z) = solve(n, c, m, p, b);
        printf("Case #%d: %d %d\n", x+1, y, z);
    }
    return 0;
}

smallだけ

#include <cstdio>
#include <vector>
#include <algorithm>
#include <array>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
#define repeat_from_reverse(i,m,n) for (int i = (n)-1; (i) >= int(m); --(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
#define debug(x) #x << " = " << (x) << " "
using ll = long long;
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }


// http://www.prefield.com/algorithm/basic/template.html
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

// http://www.prefield.com/algorithm/graph/graph.html
struct Edge {
  int src, dst;
  Edge(int src, int dst) :
    src(src), dst(dst) { }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

// http://www.prefield.com/algorithm/graph/maximum_matching.html + a
#define EVEN(x) (mu[x] == x || (mu[x] != x && phi[mu[x]] != mu[x]))
#define ODD(x)  (mu[x] != x && phi[mu[x]] == mu[x] && phi[x] != x)
#define OUTER(x) (mu[x] != x && phi[mu[x]] == mu[x] && phi[x] == x)
int maximumMatching(const Graph &g) {
  int n = g.size();
  vector<int> mu(n), phi(n), rho(n), scanned(n);
  REP(v,n) mu[v] = phi[v] = rho[v] = v; // (1) initialize
  for (int x = -1; ; ) {
    if (x < 0) {                        // (2) select even
      for (x = 0; x < n && (scanned[x] || !EVEN(x)); ++x);
      if (x == n) break;
    }
    int y = -1;                         // (3) select incident
    FOR(e, g[x]) if (OUTER(e->dst) || (EVEN(e->dst) && rho[e->dst] != rho[x])) y = e->dst;
    if (y == -1) scanned[x] = true, x = -1;
    else if (OUTER(y)) phi[y] = x;      // (4) growth
    else {
      vector<int> dx(n, -2), dy(n, -2); // (5,6), !TRICK! x % 2 --> x >= 0
      for (int k = 0, w = x; dx[w] < 0; w = k % 2 ? mu[w] : phi[w]) dx[w] = k++;
      for (int k = 0, w = y; dy[w] < 0; w = k % 2 ? mu[w] : phi[w]) dy[w] = k++;
      bool vertex_disjoint = true;
      REP(v,n) if (dx[v] >= 0 && dy[v] > 0) vertex_disjoint = false;
      if (vertex_disjoint) {            // (5) augment
        REP(v,n) if (dx[v] % 2) mu[phi[v]] = v, mu[v] = phi[v];
        REP(v,n) if (dy[v] % 2) mu[phi[v]] = v, mu[v] = phi[v];
        mu[x] = y; mu[y] = x; x = -1;
        REP(v,n) phi[v] = rho[v] = v, scanned[v] = false;
      } else {                          // (6) shrink
        int r = x, d = n;
        REP(v,n) if (dx[v] >= 0 && dy[v] >= 0 && rho[v] == v && d > dx[v]) d = dx[v], r = v;
        REP(v,n) if (dx[v] <= d && dx[v] % 2 && rho[phi[v]] != r) phi[phi[v]] = v;
        REP(v,n) if (dy[v] <= d && dy[v] % 2 && rho[phi[v]] != r) phi[phi[v]] = v;
        if (rho[x] != r) phi[x] = y;
        if (rho[y] != r) phi[y] = x;
        REP(v,n) if (dx[rho[v]] >= 0 || dy[rho[v]] >= 0) rho[v] = r;
      }
    }
  }
  Edges matching;
  REP(u,n) if (u < mu[u]) matching.push_back( Edge(u, mu[u]) );
  return matching.size(); // make explicit matching
}


pair<int, int> solve(int n, int c, int m, vector<int> const & p, vector<int> const & b) {
    if (c != 2) return make_pair(-1, -1);
    Graph g(m);
    repeat (i,m) {
        repeat (j,m) {
            if (b[i] != b[j] and not (p[i] == 0 and p[j] == 0)) {
                g[i].push_back(Edge(i, j));
            }
        }
    }
    int y = maximumMatching(g);
    y = y + (m-2*y);
    g = Graph(m);
    repeat (i,m) {
        repeat (j,m) {
            if (b[i] != b[j] and p[i] != p[j]) {
                g[i].push_back(Edge(i, j));
            }
        }
    }
    int z = maximumMatching(g);
    z = z + (m-2*z);
    return make_pair(y, z-y);
}

int main() {
    int t; scanf("%d", &t);
    repeat (x,t) {
        int n, c, m; scanf("%d%d%d", &n, &c, &m);
        vector<int> p(m), b(m); repeat (i,m) { scanf("%d%d", &p[i], &b[i]); -- p[i]; -- b[i]; }
        int y, z; tie(y, z) = solve(n, c, m, p, b);
        printf("Case #%d: %d %d\n", x+1, y, z);
    }
    return 0;
}

AtCoder Regular Contest 068: E - Snuke Line

,

http://arc068.contest.atcoder.jp/tasks/arc068_c

solution

区間$[l, r)$に累積和で足し込んで幅$d$で飛ばしながら舐めるのはすぐに思い付くが、同じ区間を複数回数えてしまってだめ。 しかしそのような事態が起こるのは$d \le r - l$のときだけなので、幅$d$で舐めるときには$r - l \lt d$な区間のみの累積和にできれば解決する。 $d \le r - l$な区間は明らかに踏むので別に数えればよい。 これは$d$を$1$から増やしながら、それに伴なって区間を追加していけばよい。 これはbinary indexed treeがあれば、$O(N + M \log M)$。 篩ほど速くはないが調和級数の和のオーダーは$O(\log n)$である。

implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;

template <class Monoid>
struct segment_tree {
    typedef typename Monoid::type T;
    int n;
    vector<T> a;
    Monoid mon;
    segment_tree() = default;
    segment_tree(int a_n, Monoid const & a_mon = Monoid()) : mon(a_mon) {
        n = 1; while (n < a_n) n *= 2;
        a.resize(2*n-1, mon.unit);
    }
    void point_update(int i, T z) { // 0-based
        a[i+n-1] = z;
        for (i = (i+n)/2; i > 0; i /= 2) {
            a[i-1] = mon.append(a[2*i-1], a[2*i]);
        }
    }
    T range_concat(int l, int r) { // 0-based, [l, r)
        T lacc = mon.unit, racc = mon.unit;
        for (l += n, r += n; l < r; l /= 2, r /= 2) { // loop, 2x faster than recursion
            if (l % 2 == 1) lacc = mon.append(lacc, a[(l ++) - 1]);
            if (r % 2 == 1) racc = mon.append(a[(-- r) - 1], racc);
        }
        return mon.append(lacc, racc);
    }
};
struct plus_t {
    typedef int type;
    const int unit = 0;
    int append(int a, int b) { return a + b; }
};

int main() {
    int n, m; scanf("%d%d", &n, &m);
    vector<int> l(n), r(n); repeat (i,n) { scanf("%d%d", &l[i], &r[i]); ++ r[i]; }
    vector<int> length_order(n);
    whole(iota, length_order, 0);
    whole(sort, length_order, [&](int i, int j) { return r[i] - l[i] < r[j] - l[j]; });
    vector<int> result(m+1);
    segment_tree<plus_t> segtree(m+2); // or a binary indexed tree
    int i = 0;
    repeat_from (d,1,m+1) {
        result[d] += n - i;
        for (int x = 0; x <= m; x += d) {
            result[d] += segtree.range_concat(0, x+1);
        }
        for (; i < n and r[length_order[i]] - l[length_order[i]] <= d; ++ i) {
            int li = l[length_order[i]];
            int ri = r[length_order[i]];
            segtree.point_update(li, segtree.range_concat(li, li+1) + 1);
            segtree.point_update(ri, segtree.range_concat(ri, ri+1) - 1);
        }
    }
    repeat_from (d,1,m+1) {
        printf("%d\n", result[d]);
    }
    return 0;
}

AtCoder Regular Contest 068: D - Card Eater

,

http://arc068.contest.atcoder.jp/tasks/arc068_b

solution

余剰カードの枚数を$b$、それ以外のカードの枚数(つまり書かれた値の種類数)を$a$とすると答えは$a - (b \bmod 2)$。 整列するから$O(N \log N)$あるいは$O(\max A_i)$。

値$A, B$が書かれたカードがそれぞれ複数枚あるとき、$A, A, B$あるいは$A, B, B$とすれば両方を$1$枚ずつ減らせる。 これは$A = B$でもよい。 よって、最後に$1$枚余るかどうかだけ考えればよい。

implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;
int main() {
    int n; scanf("%d", &n);
    vector<int> a(n); repeat (i,n) scanf("%d", &a[i]);
    whole(sort, a);
    int n_unique = whole(unique, a) - a.begin();
    int n_duplicated = n - n_unique;
    int ans = n_unique - (n_duplicated % 2 == 0 ? 0 : 1);
    printf("%d\n", ans);
    return 0;
}



Codeforces Round #375 (Div. 2): E. One-Way Reform

,

http://codeforces.com/contest/723/problem/E

solution

奇数次数の頂点の間に適当に辺を張り全て偶数次数にし、辺集合を適当に閉路に分割し、それぞれの閉路を勝手に有向閉路化すればよい。奇数次数の頂点の間に張った辺は出力の際には取り除く。$O(N^3)$。

答えの整数は偶数次数の頂点数を越えないことは明らか。 上の手順で全ての偶数次数の頂点が、入次数と出次数が等しいものになることを確認すればよい。 これは有向閉路上の頂点ということから言える。

implementation

#include <cstdio>
#include <vector>
#include <functional>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

pair<int, vector<pair<int, int> > > solve(int n, vector<vector<int> > const & g) {
    vector<vector<bool> > is_original = vectors(n, n, false); // adjacency matrix
    repeat (i,n) for (int j : g[i]) is_original[i][j] = true;
    vector<vector<int> > h = vectors(n, n, 0); // adjacency matrix
    repeat (i,n) for (int j : g[i]) h[i][j] += 1;
    vector<bool> used(n); // of vertices
    vector<pair<int, int> > result;
    repeat (root,n) if (not used[root]) {
        // split to components
        vector<bool> connected(n);
        function<void (int)> connect = [&](int i) {
            used[i] = true;
            connected[i] = true;
            for (int j : g[i]) if (not used[j]) {
                connect(j);
            }
        };
        connect(root);
        // connect odd-degree vertices
        vector<int> odds;
        repeat (i,n) if (connected[i]) {
            if (g[i].size() % 2 == 1) {
                odds.push_back(i);
            }
        }
        assert (odds.size() % 2 == 0);
        repeat (k, odds.size() / 2) {
            int i = odds[2*k  ];
            int j = odds[2*k+1];
            h[i][j] += 1;
            h[j][i] += 1;
        }
        // orient edges
        function<void (int, int)> orient = [&](int i, int j) {
            if (is_original[i][j]) {
                result.emplace_back(i, j);
                is_original[i][j] = false;
                is_original[j][i] = false;
            }
            h[i][j] -= 1;
            h[j][i] -= 1;
        };
        function<void (int, int)> go = [&](int i, int root) {
            repeat (j,n) if (h[i][j]) {
                orient(i, j);
                if (j != root) {
                    go(j, root);
                }
                return;
            }
            assert (false);
        };
        repeat (i,n) if (connected[i]) {
            repeat (j,n) while (h[i][j]) {
                orient(i, j);
                go(j, i);
            }
        }
    }
    int cnt = 0;
    repeat (i,n) cnt += (g[i].size() % 2 == 0);
    return make_pair(cnt, result);
}

int main() {
    int t; scanf("%d", &t);
    while (t --) {
        int n, m; scanf("%d%d", &n, &m);
        vector<vector<int> > g(n);
        repeat (i,m) {
            int u, v; scanf("%d%d", &u, &v); -- u; -- v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        int cnt; vector<pair<int, int> > result; tie(cnt, result) = solve(n, g);
        printf("%d\n", cnt);
        for (auto e : result) {
            int i, j; tie(i, j) = e;
            printf("%d %d\n", i+1, j+1);
        }
    }
    return 0;
}

Google Code Jam Distributed Round 1 2017: E. query_of_death

,

https://code.google.com/codejam/contest/8314486/dashboard#s=p4

全完$45$位という大勝利だった。

solution

各ノードに区間を割り当て左から順に(単純に)舐め、その後壊れているか確認をする。 壊れたノードの担当していた区間を壊れていない残りのノードに再度分配し、これをそれぞれ右から舐める。 区間長は$\frac{1}{K}$になっているので、今回は各点ごとに確認をする。 悪いクエリの位置$i_{\mathrm{qod}}$が分かるので、これをまとめ上げれば答え。 長さ$N$と確認の回数$c$とノード数$K$に対し$O(\frac{N + c}{K} + K + \frac{Nc}{K^2})$。

今回は$2$段で止めたが最後まで再帰でやるのもよいかもしれない。

implementation

$K = 100$で$N \le 10^8$。確認回数$c = 100$は多すぎるかなと思ったが$478$msなので余裕はあったらしい。なお制限時間は$2$sec。

#include "message.h"
#include "query_of_death.h"
#include <cstdio>
#include <vector>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;

int main() {
    const int root_node_id = 0;
    const int number_of_nodes = NumberOfNodes();
    const int my_node_id = MyNodeId();
    int n = GetLength();
    vector<bool> value;
    { // on each node
        int l = (n *(ll)  my_node_id     ) / number_of_nodes;
        int r = (n *(ll) (my_node_id + 1)) / number_of_nodes;
        value.resize(r-l);
        repeat (i,r-l) {
            value[i] = GetValue(l+i);
        }
        bool is_broken = false;
        if (not value.empty()) {
            repeat (iteration, 100) {
                if (GetValue(l) != value[0]) {
                    is_broken = true;
                }
            }
        }
        int message = whole(count, value, true);
        if (is_broken) message = -1;
        PutInt(root_node_id, message);
        Send(root_node_id);
    }
    if (my_node_id == root_node_id) { // sum up
        int sum = 0;
        int broken_node_id = -1;
        repeat (node_id, number_of_nodes) {
            Receive(node_id);
            int message = GetInt(node_id);
            if (message == -1) {
                broken_node_id = node_id;
            } else {
                sum += message;
            }
        }
        repeat (node_id, number_of_nodes) {
            PutInt(node_id, broken_node_id);
            Send(node_id);
        }
        PutInt(broken_node_id, sum);
        Send(broken_node_id);
    }
    // on each node
    Receive(root_node_id);
    int broken_node_id = GetInt(root_node_id);
    int broken_l = (n *(ll)  broken_node_id     ) / number_of_nodes;
    int broken_r = (n *(ll) (broken_node_id + 1)) / number_of_nodes;
    if (my_node_id != broken_node_id) {
        int updated_node_id = my_node_id - (broken_node_id < my_node_id);
        int l = broken_l + ((broken_r - broken_l) *(ll)  updated_node_id     ) / (number_of_nodes - 1);
        int r = broken_l + ((broken_r - broken_l) *(ll) (updated_node_id + 1)) / (number_of_nodes - 1);
        int qod = -1;
        value.clear();
        value.resize(r-l);
        repeat_reverse (i,r-l) {
            value[i] = GetValue(l+i);
            repeat (iteration, 100) {
                if (GetValue(l+i) != value[i]) {
                    qod = l+i;
                    value[i] = false;
                    break;
                }
            }
            if (qod != -1) break;
        }
        int message = whole(count, value, true);
        PutInt(broken_node_id, message);
        PutInt(broken_node_id, qod);
        Send(broken_node_id);
    } else {
        Receive(root_node_id);
        int sum = GetInt(root_node_id);
        repeat_reverse (node_id, number_of_nodes) if (node_id != broken_node_id) {
            Receive(node_id);
            int message = GetInt(node_id);
            int qod = GetInt(node_id);
            sum += message;
            if (qod != -1) {
                sum += count(value.begin(), value.begin() + (qod - broken_l + 1), true);
                break;
            }
        }
        printf("%d\n", sum);
    }
    return 0;
}

Google Code Jam Distributed Round 1 2017: D. todd_and_steven

,

https://code.google.com/codejam/contest/8314486/dashboard#s=p3

In progessな状態がscoreboard上でIncorrect扱いされるバグのせいで無駄な作業をしてしまった。

solution

各ノードに整列後の列の上の区間$[l, r)$を割り当てる。 値からそれぞれの列$A_o, A_e$上でのindexを求めるのは二分探索でできる。 整列後の列$B$の$l$項目$B_l$の値を求めるのは、上の二分探索を述語に使って再度の二分探索でできる。 $B_l$が求まれば列$A_o, A_e$上のindexをそれぞれ再度求め、そこから単純に$r-l$個読めばよい。 長さ$N_o,N_e$と要素の最大値$A_\mathrm{max}$とノード数$K$に対し$O(\frac{\log A_\mathrm{max} \cdot (\log N_o + \log N_e)}{K} + K)$。

implementation

distributedだとかまったく関係ない普通のにぶたんをバグらせて手間取っていた。

$K = 100$で$N_o, N_e \le 10^9$の制約で$1227$msだった。制限時間$4$secなことを考えると他と同じくらいらしい。

#include "message.h"
#include "todd_and_steven.h"
#include <cstdio>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i))
using ll = long long;
using namespace std;

constexpr ll inf = ll(1e18)+9;
template <typename F>
ll GetLowerBoundIndexForValue(ll value, int n, F GetValue) {
    ll l = -1, r = n; // (l, r]
    while (r - l >= 2) {
        ll m = (l + r) / 2;
        ll result = m < n ? GetValue(m) : inf;
        (result >= value ? r : l) = m;
    }
    return r;
}
ll GetLowerBoundValueForIndex(ll index, int todd_length, int steven_length) {
    ll l = -1, r = 5ll*1e9; // (l, r]
    while (r - l >= 2) {
        ll m = (l + r) / 2;
        ll j =
            GetLowerBoundIndexForValue(m, todd_length, GetToddValue)
            + GetLowerBoundIndexForValue(m, steven_length, GetStevenValue);
        (j >= index ? r : l) = m;
    }
    return r;
}

constexpr ll mod = 1e9+7;
int main() {
    const int number_of_nodes = NumberOfNodes();
    const int my_node_id = MyNodeId();
    int todd_length = GetToddLength();
    int steven_length = GetStevenLength();
    ll n = todd_length + steven_length;
    { // on each node
        ll l = (n *  my_node_id     ) / number_of_nodes;
        ll r = (n * (my_node_id + 1)) / number_of_nodes;
        ll value = GetLowerBoundValueForIndex(l, todd_length, steven_length);
        ll todd_index = GetLowerBoundIndexForValue(value, todd_length, GetToddValue);
        ll steven_index = GetLowerBoundIndexForValue(value, steven_length, GetStevenValue);
        ll todd_value, steven_value;
        auto update_todd_value = [&]() {
            todd_value = todd_index < todd_length ? GetToddValue(todd_index) : inf;
            ++ todd_index;
        };
        auto update_steven_value = [&]() {
            steven_value = steven_index < steven_length ? GetStevenValue(steven_index) : inf;
            ++ steven_index;
        };
        update_todd_value();
        update_steven_value();
        ll result = 0;
        repeat_from (i,l,r) {
            if (todd_value < steven_value) {
                result += (todd_value ^ i);
                update_todd_value();
            } else {
                result += (steven_value ^ i);
                update_steven_value();
            }
        }
        result %= mod;
        PutLL(0, result);
        Send(0);
    }
    if (my_node_id == 0) { // sum up
        ll result = 0;
        repeat (node_id, number_of_nodes) {
            Receive(node_id);
            result += GetLL(node_id);
        }
        result %= mod;
        printf("%lld\n", result);
    }
    return 0;
}

Google Code Jam Distributed Round 1 2017: C. weird_editor

,

https://code.google.com/codejam/contest/8314486/dashboard#s=p2

solution

各区間ごとに個別の文字列として見て処理すると、その結果は文字列$9^{k_9}8^{k_8}7^{k_7}6^{k_6}5^{k_5}4^{k_4}3^{k_3}2^{k_2}1^{k_1}0^{k_0}$の形をしている。 実際には$0$は全体の文字列の末尾に動くが、後の処理で同じことになるのでこれでよい。 これは整数$k_9, \dots, k_0$とすれば高速に受け渡しできて、中央ノードで同様に再度処理すればよい。 長さ$N$とノード数$K$に対し$O(\frac{N}{K} + K)$。

implementation

$K = 100$かつ$N \le 10^9$。今回$867$ms。定数として数字の種類$k = 10$が乗ってるからこれぐらいが妥当。 しかしGetDigit(i)の呼び出しは$0.11$usらしいので$\frac{N}{K} \le 10^7$回呼んだら固定で$1100$msかかるはずなのだけど、妙に速い。

#include "message.h"
#include "weird_editor.h"
#include <cstdio>
#include <array>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
using ll = long long;
using namespace std;

ll powmod(ll x, ll y, ll p) { // O(log y)
    assert (0 <= x and x < p);
    assert (0 <= y);
    ll z = 1;
    for (ll i = 1; i <= y; i <<= 1) {
        if (y & i) z = z * x % p;
        x = x * x % p;
    }
    return z;
}
ll repunit(ll n, ll p) {
    ll y = 0;
    ll x = 1;
    for (ll i = 1; i <= n; i <<= 1) {
        if (n & i) y = (y * powmod(10, i, p) % p + x) % p;
        x = (x * powmod(10, i, p) % p + x) % p;
    }
    return y;
}

constexpr ll mod = 1e9+7;
int main() {
    const int number_of_nodes = NumberOfNodes();
    const int my_node_id = MyNodeId();
    int n = GetNumberLength();
    { // on each node
        int l = (n *(ll)  my_node_id     ) / number_of_nodes;
        int r = (n *(ll) (my_node_id + 1)) / number_of_nodes;
        array<int, 10> cnt = {};
        repeat_from (i,l,r) {
            int d = GetDigit(i);
            assert (0 <= d and d <= 9);
            cnt[d] += 1;
            repeat_from (e,1,d) {
                cnt[0] += cnt[e];
                cnt[e] = 0;
            }
        }
        repeat (d,10) {
            PutInt(0, cnt[d]);
        }
        Send(0);
    }
    if (my_node_id == 0) { // sum up
        array<int, 10> cnt = {};
        repeat (node_id, number_of_nodes) {
            Receive(node_id);
            array<int, 10> ds;
            repeat (d,10) {
                ds[d] = GetInt(node_id);
            }
            repeat_reverse (d,10) if (ds[d]) {
                cnt[d] += ds[d];
                repeat_from (e,1,d) {
                    cnt[0] += cnt[e];
                    cnt[e] = 0;
                }
            }
        }
        ll result = 0;
        repeat_reverse (d,10) {
            result = result * powmod(10, cnt[d], mod) % mod;
            result = (result + d *(ll) repunit(cnt[d], mod) % mod) % mod;
        }
        printf("%lld\n", result);
    }
    return 0;
}

Google Code Jam Distributed Round 1 2017: B. pancakes

,

https://code.google.com/codejam/contest/8314486/dashboard#s=p1

sampleを切り替えるのはsymbolic linkの貼り替えでしてたけど、もうちょっといい方法ないだろうか。

solution

revolutionで区切ると面倒なので移動で区切る。 各ノードに$[0, N)$の区間を分配し、区間$[l, r)$を担当するノードは$\mathrm{Item}_{l-1}$から$\mathrm{Item}_{r}$へ全て配り終えた後に移動するときの距離を計算するようにする。 $\mathrm{Item}_0 = 0, \; \mathrm{Item}_N = D-1$としておいて、全て足して$1$加えて$D$で割れば答え。 stack size $N$とノード数$K$に対し$O(\frac{N}{K} + K)$。

implementation

$K = 100$で$N \le 10^8$なのに$759$msなのは、GetStackItem(i)の$0.8$usにより$800$ms固定で乗るからだろう。 むしろこれより速いのはなぜなのか。

#include "message.h"
#include "pancakes.h"
#include <cstdio>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i))
using ll = long long;
using namespace std;

int main() {
    const int number_of_nodes = NumberOfNodes();
    const int my_node_id = MyNodeId();
    int n = GetStackSize();
    int d = GetNumDiners();
    { // on each node
        int l = ((n+1) *(ll)  my_node_id     ) / number_of_nodes;
        int r = ((n+1) *(ll) (my_node_id + 1)) / number_of_nodes;
        ll acc = 0;
        int cur = (l == 0 ? 0 : GetStackItem(l-1));
        repeat_from (i,l,r) {
            int nxt = i == n ? d-1 : GetStackItem(i);
            if (cur <= nxt) {
                acc += nxt - cur;
                cur = nxt;
            } else {
                acc += d + nxt - cur;
                cur = nxt;
            }
        }
        PutLL(0, acc);
        Send(0);
    }
    if (my_node_id == 0) { // sum up
        ll acc = 0;
        repeat (node_id, number_of_nodes) {
            Receive(node_id);
            acc += GetLL(node_id);
        }
        assert ((acc + 1) % d == 0);
        ll result = (acc + 1) / d;
        printf("%lld\n", result);
    }
    return 0;
}

Google Code Jam 2017 Round 2: C. Beaming With Joy

,

https://code.google.com/codejam/contest/5314486/dashboard#s=p2

dir_t mirror(char c, dir_t d) {
    ...
            case RIGHT: return DOWN;
            case LEFT: return UP;
    ...
}

であるところを、

            case RIGHT: return UP;
            case LEFT: return DOWN;

としてlargeを落としました。 Tシャツは増えたとはいえ、これがなかったらRound 3だったのでとても残念。

solution

$3$-satにしてsolverに投げる。計算量はとりあえず$O(2^{HW})$。

変数を用意する: 砲台が水平であるかどうかを$v_i$、ある点を光線が通っているかを$w_{y,x}$とする。 点$(y, x)$を光線が通るような砲台の番号と向きを列挙し$x_1, \dots, x_k$として、項$\lnot (\lnot x_1 \land \dots \land \lnot x_k) \to \lnot w_{y,x}$および項$w_{y,x}$を制約式に追加する。 あとはこれを解けばよい。

実際は$2$-satで十分。ある点を通る光線が$3$つ以上あれば、砲台は破壊されないという制約に違反するため。$3$-satでも十分賢ければ内部で$O(HW)$ぐらいに落ちていそう。

implementation

Togasatを利用した: https://github.com/togatoga/Togasat @ 00d8a82cbf2b91d36c990fb6e101e5d49357d96d

#include <iostream>
#include <vector>
#include <functional>
#include <cassert>
#include "Solver.hpp"
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

enum dir_t { UP, DOWN, RIGHT, LEFT };
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, 1, -1 };
dir_t mirror(char c, dir_t d) {
    if (c == '/') {
        switch (d) {
            case UP: return RIGHT;
            case DOWN: return LEFT;
            case RIGHT: return UP;
            case LEFT: return DOWN;
        }
    } else if (c == '\\') {
        switch (d) {
            case UP: return LEFT;
            case DOWN: return RIGHT;
            case RIGHT: return DOWN;
            case LEFT: return UP;
        }
    }
    assert (false);
}

vector<string> solve(int h, int w, vector<string> const & s) {
    // analyze the field
    auto is_on_field = [&](int y, int x) { return 0 <= y and y < h and 0 <= x and x < w; };
    vector<pair<int, int> > shooters;
    repeat (y,h) {
        repeat (x,w) {
            if (s[y][x] == '-' or s[y][x] == '|') {
                shooters.emplace_back(y, x);
            }
        }
    }
    function<bool (int, int, dir_t, vector<pair<int, int> > &)> shoot = [&](int y, int x, dir_t d, vector<pair<int, int> > & acc) {
        int ny = y + dy[d];
        int nx = x + dx[d];
        if (not is_on_field(ny, nx) or s[ny][nx] == '#') { // goal
            return true;
        } else if (s[ny][nx] == '.') {
            acc.emplace_back(ny, nx);
            return shoot(ny, nx, d, acc);
        } else if (s[ny][nx] == '/' or s[ny][nx] == '\\') {
            return shoot(ny, nx, mirror(s[ny][nx], d), acc);
        } else if (s[ny][nx] == '-' or s[ny][nx] == '|') {
            acc.clear();
            return false;
        } else {
            assert (false);
        }
    };
    vector<char> shooter_result(shooters.size(), '\0');
    auto used = vectors(h, w, bool());
    auto vars = vectors(h, w, vector<int>());
    repeat (i, shooters.size()) {
        int y, x; tie(y, x) = shooters[i];
        vector<pair<int, int> > a, b;
        bool is_hr = shoot(y, x, RIGHT, a) and shoot(y, x, LEFT, a);
        bool is_vr = shoot(y, x, UP, b) and shoot(y, x, DOWN, b);
        if (not is_hr and not is_vr) {
            return vector<string>(); // IMPOSSIBLE
        } else if (not is_hr or not is_vr) {
            shooter_result[i] = (is_hr ? '-' : '|');
            if (a.empty()) a.swap(b);
            for (auto it : a) {
                int ay, ax; tie(ay, ax) = it;
                used[ay][ax] = true;
            }
        } else {
            for (auto it : a) {
                int ay, ax; tie(ay, ax) = it;
                vars[ay][ax].push_back(+ (i+1));
            }
            for (auto it : b) {
                int by, bx; tie(by, bx) = it;
                vars[by][bx].push_back(- (i+1));
            }
        }
    }
    // sat
    togasat::Solver solver;
    auto var_at = [&](int y, int x) { return 1 + shooters.size() + y * h + x; };
    vector<pair<int, int> > cnf;
    repeat (i, shooters.size()) {
        int x = i+1;
        vector<int> tautology;
        tautology.push_back(+ x);
        tautology.push_back(- x);
        solver.addClause(tautology);
    }
    repeat (y,h) {
        repeat (x,w) if (s[y][x] == '.' and not used[y][x]) {
            vector<int> clause = vars[y][x];
            clause.push_back(- var_at(y, x));
            solver.addClause(clause);
            vector<int> assertion;
            assertion.push_back(var_at(y, x));
            assertion.push_back(var_at(y, x));
            solver.addClause(assertion);
        }
    }
    togasat::lbool status = solver.solve();
    if (status != 0) return vector<string>(); // IMPOSSIBLE
    repeat (i, shooters.size()) if (not shooter_result[i]) {
        shooter_result[i] = (solver.assigns[i] ? '|' : '-');
    }
    // result
    vector<string> result = s;
    repeat (i, shooters.size()) {
        int y, x; tie(y, x) = shooters[i];
        result[y][x] = shooter_result[i];
    }
    return result;
}

int main() {
    int t; cin >> t;
    repeat (x,t) {
        int h, w; cin >> h >> w;
        vector<string> s(h); repeat (y,h) cin >> s[y];
        vector<string> result;
        result = solve(h, w, s);
        cout << "Case #" << x+1 << ": " << (result.empty() ? "IMPOSSIBLE" : "POSSIBLE") << endl;
        if (not result.empty()) {
            repeat (y,h) cout << result[y] << endl;
        }
    }
    return 0;
}