#857541 (C++17) No.2263 Perms

提出ソース

結果

問題	No.2263 Perms
ユーザー	hari64
提出日時	2023-04-07 22:38:49
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	11,888 bytes
コンパイル時間	2,463 ms
コンパイル使用メモリ	218,656 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-10-02 20:02:29
合計ジャッジ時間	4,314 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	WA	-
testcase_05	AC	3 ms 5,248 KB
testcase_06	AC	11 ms 5,248 KB
testcase_07	AC	9 ms 5,248 KB
testcase_08	AC	9 ms 5,248 KB
testcase_09	AC	10 ms 5,248 KB
testcase_10	WA	-
testcase_11	AC	11 ms 5,248 KB
testcase_12	AC	11 ms 5,248 KB
testcase_13	AC	11 ms 5,248 KB
testcase_14	AC	12 ms 5,248 KB
testcase_15	AC	2 ms 5,248 KB
testcase_16	AC	2 ms 5,248 KB
testcase_17	AC	2 ms 5,248 KB
testcase_18	AC	3 ms 5,248 KB
testcase_19	AC	3 ms 5,248 KB
testcase_20	AC	9 ms 5,248 KB
testcase_21	AC	9 ms 5,248 KB
testcase_22	AC	7 ms 5,248 KB
testcase_23	AC	4 ms 5,248 KB
testcase_24	AC	3 ms 5,248 KB
testcase_25	AC	9 ms 5,248 KB
testcase_26	AC	10 ms 5,248 KB
testcase_27	AC	5 ms 5,248 KB
testcase_28	AC	3 ms 5,248 KB
testcase_29	AC	4 ms 5,248 KB
testcase_30	AC	2 ms 5,248 KB
testcase_31	AC	2 ms 5,248 KB
testcase_32	AC	3 ms 5,248 KB
testcase_33	AC	3 ms 5,248 KB
testcase_34	AC	2 ms 5,248 KB
testcase_35	AC	2 ms 5,248 KB
testcase_36	AC	3 ms 5,248 KB
testcase_37	AC	2 ms 5,248 KB
testcase_38	AC	8 ms 5,248 KB
testcase_39	AC	2 ms 5,248 KB
testcase_40	AC	2 ms 5,248 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#ifndef hari64
#include <bits/stdc++.h>
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#define debug(...)
#else
#include "util/viewer.hpp"
#define debug(...) viewer::_debug(__LINE__, #__VA_ARGS__, __VA_ARGS__)
#endif
using namespace std;
constexpr int INF = 1001001001;
constexpr long long INFll = 1001001001001001001;
template <class T>
bool chmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    return a > b ? a = b, 1 : 0;
}

struct Xor128 {  // period 2^128 - 1
    uint32_t x, y, z, w;
    static constexpr uint32_t min() { return 0; }
    static constexpr uint32_t max() { return UINT32_MAX; }
    Xor128(uint32_t seed = 0)
        : x(123456789), y(362436069), z(521288629), w(88675123 + seed) {}
    uint32_t operator()() {
        uint32_t t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }
    uint32_t operator()(uint32_t l, uint32_t r) { return ((*this)() % (r - l)) + l; }
    uint32_t operator()(uint32_t r) { return (*this)() % r; }
};
struct Rand {  // https://docs.python.org/ja/3/library/random.html
    Rand(){};
    Rand(int seed) : gen(seed){};
    // シードを変更します
    inline void set_seed(int seed) {
        Xor128 _gen(seed);
        gen = _gen;
    }
    // ランダムな浮動小数点数（範囲は[0.0, 1.0)) を返します
    inline double random() { return (double)gen() / (double)gen.max(); }
    // a <= b であれば a <= N <= b 、b < a であれば b <= N <= a
    // であるようなランダムな浮動小数点数 N を返します
    inline double uniform(double a, double b) {
        if (b < a) swap(a, b);
        return a + (b - a) * double(gen()) / double(gen.max());
    }
    // range(0, stop) の要素からランダムに選ばれた要素を返します
    inline uint32_t randrange(uint32_t r) { return gen(r); }
    // range(start, stop) の要素からランダムに選ばれた要素を返します
    inline uint32_t randrange(uint32_t l, uint32_t r) { return gen(l, r); }
    // a <= N <= b であるようなランダムな整数 N を返します randrange(a, b + 1)
    // のエイリアスです
    inline uint32_t randint(uint32_t l, uint32_t r) { return gen(l, r + 1); }
    // シーケンス x をインプレースにシャッフルします
    template <class T>
    void shuffle(vector<T>& x) {
        for (int i = x.size(), j; i > 1;) {
            j = gen(i);
            swap(x[j], x[--i]);
        }
    }
    // 空でないシーケンス seq からランダムに要素を返します
    template <class T>
    T choice(const vector<T>& seq) {
        assert(!seq.empty());
        return seq[gen(seq.size())];
    }
    // 相対的な重みに基づいて要素が選ばれます (※複数回呼ぶ場合は処理を変えた方が良い)
    template <class T, class U>
    T choice(const vector<T>& seq, const vector<U>& weights) {
        assert(seq.size() == weights.size());
        vector<U> acc(weights.size());
        acc[0] = weights[0];
        for (int i = 1; i < int(weights.size()); i++) acc[i] = acc[i - 1] + weights[i];
        return seq[lower_bound(acc.begin(), acc.end(), random() * acc.back()) -
                   acc.begin()];
    }
    // 母集団のシーケンスまたは集合から選ばれた長さ k
    // の一意な要素からなるリストを返します 重複無しのランダムサンプリングに用いられます
    template <class T>
    vector<T> sample(const vector<T>& p, int k) {
        int j, i = 0, n = p.size();
        assert(0 <= k && k <= n);
        vector<T> ret(k);
        unordered_set<int> s;
        for (; i < k; i++) {
            do {
                j = gen(n);
            } while (s.find(j) != s.end());
            s.insert(j);
            ret[i] = p[j];
        }
        return ret;
    }
    // 正規分布です mu は平均で sigma は標準偏差です
    double normalvariate(double mu = 0.0, double sigma = 1.0) {
        double u2, z, NV = 4 * exp(-0.5) / sqrt(2.0);
        while (true) {
            u2 = 1.0 - random();
            z = NV * (random() - 0.5) / u2;
            if (z * z / 4.0 <= -log(u2)) break;
        }
        return mu + z * sigma;
    }

   private:
    Xor128 gen;
} myrand;

// clang-format off
template<class T>
struct simple_queue{vector<T>payload;int pos=0;void reserve(int n){payload.reserve(n);}int size()const{return int(payload.size())-pos;}bool empty()const{return pos==int(payload.size());}void push(const T&t){payload.push_back(t);}T&front(){return payload[pos];}void clear(){payload.clear();pos=0;}void pop(){pos++;}};
template<class Cap=long long>
struct mf_graph{
    mf_graph():_n(0){};explicit mf_graph(int n):_n(n),g(n){};struct edge{int from,to;Cap cap,flow;};
    // fromからtoへ最大容量cap、流量 0 の辺を追加し、何番目に追加された辺かを返す
    int add_edge(int from,int to,Cap cap){assert(0<=from&&from<_n);assert(0<=to&&to<_n);assert(0<=cap);int m=int(pos.size());pos.push_back({from,int(g[from].size())});int from_id=int(g[from].size());int to_id=int(g[to].size());if(from==to)to_id++;g[from].push_back(_edge{to,to_id,cap});g[to].push_back(_edge{from,from_id,0});return m;}
    // 今の内部の辺の状態を返す 辺の順番はadd_edgeで追加された順番と同一
    edge get_edge(int i){assert(0<=i&&i<int(pos.size()));auto _e=g[pos[i].first][pos[i].second];auto _re=g[_e.to][_e.rev];return edge{pos[i].first,_e.to,_e.cap+_re.cap,_re.cap};}
    // 今の内部の辺の状態を返す 辺の順番はadd_edgeで追加された順番と同一
    vector<edge>edges(){vector<edge>result;for(int i=0;i<int(pos.size());i++){result.push_back(get_edge(i));}return result;}
    // i 番目に追加された辺の容量、流量をnew_cap, new_flowに変更する 他の辺の容量、流量は変更しない
    void change_edge(int i,Cap new_cap,Cap new_flow){int m=int(pos.size());assert(0<=i&&i<m);assert(0<=new_flow&&new_flow<=new_cap);auto&_e=g[pos[i].first][pos[i].second];auto&_re=g[_e.to][_e.rev];_e.cap=new_cap-new_flow;_re.cap=new_flow;}
    // 頂点 s から t へ流せる限り流し、流せた量を返す 複数回呼ぶことも可能
    Cap flow(int s,int t){return flow(s,t,numeric_limits<Cap>::max());}
    // 頂点 s から t へ流量 flow_limit に達するまで流せる限り流し、 流せた量を返す  複数回呼ぶことも可能
    Cap flow(int s,int t,Cap flow_limit){assert(0<=s&&s<_n);assert(0<=t&&t<_n);assert(s!=t);vector<int>level(_n),iter(_n);simple_queue<int>que;
        auto bfs=[&](){fill(level.begin(),level.end(),-1);level[s]=0;que.clear();que.push(s);while(!que.empty()){int v=que.front();que.pop();for(auto e:g[v]){if(e.cap==0||level[e.to]>=0)continue;level[e.to]=level[v]+1;if(e.to==t)return;que.push(e.to);}}};
        auto dfs=[&](auto self,int v,Cap up){if(v==s)return up;Cap res=0;int level_v=level[v];for(int&i=iter[v];i<int(g[v].size());i++){_edge&e=g[v][i];if(level_v<=level[e.to]||g[e.to][e.rev].cap==0)continue;Cap d=self(self,e.to,min(up-res,g[e.to][e.rev].cap));if(d<=0)continue;g[v][i].cap+=d;g[e.to][e.rev].cap-=d;res+=d;if(res==up)return res;}level[v]=_n;return res;};
        Cap flow=0;while(flow<flow_limit){bfs();if(level[t]==-1)break;fill(iter.begin(),iter.end(),0);Cap f=dfs(dfs,t,flow_limit-flow);if(!f)break;flow+=f;}return flow;}
    // 長さ n のvectorを返す i 番目の要素には、頂点 s から i へ残余グラフで到達可能なとき、またその時のみ true を返す
    // flow(s,t)をflow_limitなしでちょうど一回呼んだ後に呼ぶと、返り値は s,t 間のmincutに対応します
    vector<bool>min_cut(int s){vector<bool>visited(_n);simple_queue<int>que;que.push(s);while(!que.empty()){int p=que.front();que.pop();visited[p]=true;for(auto e:g[p]){if(e.cap&&!visited[e.to]){visited[e.to]=true;que.push(e.to);}}}return visited;}
    // debug用
    string state(){string ret("\n");for(auto&e:edges())ret+="[from,to/cap,flow]:"+to_string(e.from)+","+to_string(e.to)+"/"+to_string(e.cap)+","+to_string(e.flow)+"\n";return ret;}
   private:
    int _n;struct _edge{int to,rev;Cap cap;};vector<pair<int,int>>pos;vector<vector<_edge>>g;
};
// 最小流量制限付き最大流
// ref: https://snuke.hatenablog.com/entry/2016/07/10/043918
//  s        t  S→T,s→T,S→t,s→tと流す
//   ↘     ↗   先に最小流量制限分だけ流しておくというのが基本的な考え方
//    u -> v    u → v は一つを取り出しているだけなので、逆向きの辺も存在
//     ↘↗    
//  S -   -> T  蟻本などではS→s,t→Tに∞の容量の辺を張っている
template<class Cap>
struct mf_graph_lb{
    mf_graph_lb(int n):g(n+2),S(n),T(n+1),sum_lb(0){}
    // fromからtoへ最小流量制限low、 最大容量high、流量 0 の辺を追加する
    void add_edge(int from,int to,Cap low,Cap high){assert(from!=to&&high>=low);g.add_edge(from,to,high-low);if(low!=0){g.add_edge(S,to,low);g.add_edge(from,T,low);sum_lb+=low;}}
    // 頂点 s から t へ流せる限り流し、流せた量を返す 制約を満たせない場合 -1
    Cap flow(int s,int t){assert(s!=t);Cap a=g.flow(S,T);Cap b=g.flow(s,T);Cap c=g.flow(S,t);Cap d=g.flow(s,t);debug(make_tuple(a,b,c,d));return(a+c==sum_lb&&a+b==sum_lb)?b+d:-1;}
   private:
    mf_graph<Cap>g;int S,T;Cap sum_lb;
};
// clang-format on

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    // N = myrand.randint(2, 5), M = myrand.randint(2, 5);
    cin >> N >> M;
    vector<vector<int>> As(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> As[i][j];
        }
    }
    // for (int i = 0; i < M; i++) {
    //     vector<int> Ps(N);
    //     iota(Ps.begin(), Ps.end(), 0);
    //     myrand.shuffle(Ps);
    //     for (int i = 0; i < N; i++) {
    //         As[i][Ps[i]]++;
    //     }
    // }

    {
        mf_graph g(2 * N + 2);
        int s = 2 * N;
        int t = 2 * N + 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                g.add_edge(i, N + j, As[i][j]);
            }
        }
        for (int i = 0; i < N; i++) {
            g.add_edge(s, i, M);
        }
        for (int i = 0; i < N; i++) {
            g.add_edge(N + i, t, M);
        }
        auto res = g.flow(s, t);
        debug(res);
        if (res != N * M) {
            cout << -1 << endl;
            return 0;
        }
    }

    vector<vector<int>> ans;
    for (int _ = 0; _ < M; _++) {
        mf_graph g(2 * N + 2);
        int s = 2 * N;
        int t = 2 * N + 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                g.add_edge(i, N + j, As[i][j]);
            }
        }
        for (int i = 0; i < N; i++) {
            g.add_edge(s, i, 1);
        }
        for (int i = 0; i < N; i++) {
            g.add_edge(N + i, t, 1);
        }
        auto res = g.flow(s, t, N);
        debug(res);
        if (res != N) {
            cout << -1 << endl;
            return 0;
        }
        ans.push_back({});
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                auto e = g.get_edge(i * N + j);
                if (e.flow == 1) {
                    ans.back().push_back(j + 1);
                    As[i][j]--;
                    if (As[i][j] < 0) {
                        cout << -1 << endl;
                        return 0;
                    }
                    break;
                }
            }
        }
        assert(int(ans.back().size()) == N);
    }

    for (auto& elems : ans) {
        for (auto& elem : elems) cout << elem << " ";
        cout << endl;
    }

    return 0;
}

yukicoder

結果

テストケース

ソースコード