結果

問題 No.241 出席番号(1)
ユーザー inu_hir0shiinu_hir0shi
提出日時 2015-07-10 23:27:04
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 3,851 bytes
コンパイル時間 1,478 ms
コンパイル使用メモリ 168,656 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-30 21:26:04
合計ジャッジ時間 2,691 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 1 ms
5,248 KB
testcase_09 AC 1 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 1 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 3 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 2 ms
5,248 KB
testcase_19 AC 2 ms
5,248 KB
testcase_20 AC 2 ms
5,248 KB
testcase_21 AC 1 ms
5,248 KB
testcase_22 AC 2 ms
5,248 KB
testcase_23 AC 2 ms
5,248 KB
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 2 ms
5,248 KB
testcase_26 AC 2 ms
5,248 KB
testcase_27 AC 2 ms
5,248 KB
testcase_28 AC 2 ms
5,248 KB
testcase_29 AC 2 ms
5,248 KB
testcase_30 AC 2 ms
5,248 KB
testcase_31 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
typedef unsigned long long ULL;
template<class T> inline bool amax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool amin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> ostream& operator << (ostream &os, const vector<T> &v) { os << "["; for (typename vector<T>::const_iterator it = v.begin(); it != v.end(); it++) { os << (it != v.begin() ? ", " : "") << *it; } os << "]"; return os; }
template<class T> ostream& operator << (ostream &os, const set<T> &s) { os << "{"; for (typename set<T>::const_iterator it = s.begin(); it != s.end(); it++) { os << (it != s.begin() ? ", " : "") << *it; } os << "}"; return os; }
template<class K, class V> ostream& operator << (ostream &os, const map<K, V> &m) { os << "{"; for (typename map<K, V>::const_iterator it = m.begin(); it != m.end(); it++) { os << (it != m.begin() ? ", " : "") << it->first << "->" << it->second; } os << "}"; return os; }
template<class T, class S> ostream& operator << (ostream &os, const pair<T, S> &p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template <class T> istream& operator >> (istream &is, vector<T> &v) { for (size_t i = 0; i < v.size(); i++) is >> v[i]; return is; }
template <class T, class S> inline T lexical_cast (const S &s) { T t; stringstream ss; ss << s; ss >> t; return t; }

//> v < ^ (clock wise)
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
const int INFI = 1<<28;
const long long int INFL = 1LL<<60;
const float INFF = 1e+100;
const double INFD = 1e+300;
const double EPS = 1e-8;
const long long int MOD = 1000000007;

template<class T>
struct _Edge {
    int src, dst, rev;
    T cap, cost;
    _Edge () {}
    _Edge (int dst) : dst(dst) {}  
    _Edge (int src, int dst) : src(src), dst(dst) {}  
    _Edge (int src, int dst, T cost) : src(src), dst(dst), cost(cost) {} // Dijkstra...
    _Edge (int src, int dst, T cap, int rev) : src(src), dst(dst), cap(cap), rev(rev) { } // MaxFlow
    _Edge (int src, int dst, T cap, T cost, int rev) : src(src), dst(dst), cap(cap), cost(cost), rev(rev) {} // MinCostFlow
    bool operator < (const _Edge &e) const { return e.cap < cap;  }
};
typedef _Edge<int> Edge;
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<int> Vector;
typedef vector<Vector> Matrix;

void AddEdge (Graph &G, int u, int v) {
    G[u].push_back(Edge(u, v));
    G[v].push_back(Edge(v, u));
}
bool dfs (int v, const Graph &G, vector<int> &match, vector<bool> &used) {
    used[v] = true;
    for (int i = 0; i < G[v].size(); i++) {
        int u = G[v][i].dst, w = match[u];
        if (w < 0 || !used[w] && dfs(w, G, match, used)) {
            match[v] = u;
            match[u] = v;
            return true;
        }
    }
    return false;
}

int BipartiteMatching (const Graph &G, vector<int> &match) {
    int V = G.size();
    int res = 0;
    match = vector<int>(V, -1);
    for (int v = 0; v < V; v++) {
        if (match[v] < 0) {
            vector<bool> used(V);
            if (dfs(v, G, match, used)) {
                res++;
            }
        }
    }
    return res;
}
void solve ();
int main () {
    cout.setf(ios::fixed); cout.precision(10);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

void solve () {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    Graph G(N*2);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (A[i] != j) {
                AddEdge(G, i, N+j);
            }
        }
    }
    vector<int> match;
   if (BipartiteMatching(G, match) == N) {
       for (int i = 0; i < N; i++) cout << match[i]-N << endl;
   } else {
       cout << -1 << endl;
   }
    
}
0