結果
問題 |
No.241 出席番号(1)
|
ユーザー |
|
提出日時 | 2019-11-21 03:18:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 988 bytes |
コンパイル時間 | 824 ms |
コンパイル使用メモリ | 80,096 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-08 09:28:41 |
合計ジャッジ時間 | 2,232 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
コンパイルメッセージ
main.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 49 | main() | ^~~~
ソースコード
#include<iostream> #include<set> using namespace std; #include<algorithm> #include<vector> struct bimatch{ int n; vector<vector<int> >G; vector<int>match; vector<bool>used; bimatch(int _n=0):n(_n),G(n),match(n),used(n){} void add_edge(int u,int v) { G[u].push_back(v); G[v].push_back(u); } bool dfs(int v) { used[v]=true; for(int u:G[v]) { int w=match[u]; if(w<0||!used[w]&&dfs(w)) { match[v]=u; match[u]=v; return true; } } return false; } int count() { int ans=0; bool flag=true; fill(match.begin(),match.end(),-1); while(flag) { flag=false; fill(used.begin(),used.end(),false); for(int v=0;v<n;v++)if(match[v]<0&&dfs(v))ans++,flag=true; } return ans; } }; int N; int A[50]; main() { cin>>N; bimatch P(2*N); for(int i=0;i<N;i++) { cin>>A[i]; for(int j=0;j<N;j++) { if(A[i]!=j)P.add_edge(i,N+j); } } if(P.count()!=N)cout<<-1<<endl; else { for(int i=0;i<N;i++)cout<<P.match[i]%N<<endl; } }