結果
| 問題 | No.2263 Perms |
| ユーザー |
 hari64
|
| 提出日時 | 2023-04-07 22:44:09 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 12 ms / 2,000 ms |
| コード長 | 12,240 bytes |
| コンパイル時間 | 2,710 ms |
| コンパイル使用メモリ | 223,804 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-10-02 20:06:07 |
| 合計ジャッジ時間 | 4,611 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,816 KB |
| testcase_01 | AC | 2 ms
6,820 KB |
| testcase_02 | AC | 2 ms
6,816 KB |
| testcase_03 | AC | 2 ms
6,816 KB |
| testcase_04 | AC | 2 ms
6,816 KB |
| testcase_05 | AC | 2 ms
6,820 KB |
| testcase_06 | AC | 11 ms
6,816 KB |
| testcase_07 | AC | 10 ms
6,820 KB |
| testcase_08 | AC | 9 ms
6,816 KB |
| testcase_09 | AC | 10 ms
6,820 KB |
| testcase_10 | AC | 9 ms
6,820 KB |
| testcase_11 | AC | 11 ms
6,820 KB |
| testcase_12 | AC | 11 ms
6,816 KB |
| testcase_13 | AC | 12 ms
6,816 KB |
| testcase_14 | AC | 11 ms
6,816 KB |
| testcase_15 | AC | 3 ms
6,816 KB |
| testcase_16 | AC | 2 ms
6,816 KB |
| testcase_17 | AC | 2 ms
6,820 KB |
| testcase_18 | AC | 2 ms
6,816 KB |
| testcase_19 | AC | 3 ms
6,816 KB |
| testcase_20 | AC | 9 ms
6,816 KB |
| testcase_21 | AC | 9 ms
6,820 KB |
| testcase_22 | AC | 8 ms
6,820 KB |
| testcase_23 | AC | 4 ms
6,816 KB |
| testcase_24 | AC | 3 ms
6,820 KB |
| testcase_25 | AC | 9 ms
6,816 KB |
| testcase_26 | AC | 11 ms
6,816 KB |
| testcase_27 | AC | 4 ms
6,816 KB |
| testcase_28 | AC | 3 ms
6,820 KB |
| testcase_29 | AC | 3 ms
6,816 KB |
| testcase_30 | AC | 2 ms
6,816 KB |
| testcase_31 | AC | 2 ms
6,816 KB |
| testcase_32 | AC | 3 ms
6,820 KB |
| testcase_33 | AC | 2 ms
6,816 KB |
| testcase_34 | AC | 2 ms
6,820 KB |
| testcase_35 | AC | 2 ms
6,820 KB |
| testcase_36 | AC | 2 ms
6,820 KB |
| testcase_37 | AC | 2 ms
6,816 KB |
| testcase_38 | AC | 8 ms
6,820 KB |
| testcase_39 | AC | 2 ms
6,820 KB |
| testcase_40 | AC | 2 ms
6,816 KB |
ソースコード
#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, max(0, 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);
set<int> check(ans.back().begin(), ans.back().end());
if (int(check.size()) != N) {
cout << -1 << endl;
return 0;
}
}
for (auto& elems : As) {
for (auto& e : elems) {
if (e != 0) {
cout << -1 << endl;
return 0;
}
}
}
for (auto& elems : ans) {
for (auto& elem : elems) cout << elem << " ";
cout << endl;
}
return 0;
}