結果
問題 | No.241 出席番号(1) |
ユーザー | どらら |
提出日時 | 2015-07-10 23:19:09 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,608 bytes |
コンパイル時間 | 696 ms |
コンパイル使用メモリ | 83,316 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-30 21:30:03 |
合計ジャッジ時間 | 2,011 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include <algorithm>#include <cstdio>#include <cstdlib>#include <cctype>#include <cmath>#include <iostream>#include <queue>#include <list>#include <map>#include <numeric>#include <set>#include <sstream>#include <string>#include <vector>using namespace std;#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)#define rep(i,n) REP(i,0,n)#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)#define ALLOF(c) (c).begin(), (c).end()typedef long long ll;#define MAX_V 110int V;vector<int> G[MAX_V];int match[MAX_V];bool used[MAX_V];void init_graph(){for(int i=0; i<MAX_V; i++){G[i].clear();match[i] = -1;used[i] = false;}}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 i=0; i<G[v].size(); i++){int u = G[v][i], w = match[u];if(w<0||!used[w]&&dfs(w)){match[v] = u;match[u] = v;return true;}}return false;}int bipartite_matching(){int res = 0;rep(i,MAX_V) match[i] = -1;for(int v=0; v<V; v++){if(match[v] < 0){rep(i,MAX_V) used[i] = false;if(dfs(v)){res++;}}}return res;}int main(){int N;cin >> N;vector<int> v;rep(i,N){int tmp;cin >> tmp;v.push_back(tmp);}init_graph();V = 2*N;rep(i,N){rep(j,N){if(j==v[i]) continue;add_edge(i, N+j);}}int res = bipartite_matching();if(res != N){cout << -1 << endl;return 0;}rep(i,N){cout << match[i]-N << endl;}return 0;}