結果

問題 No.241 出席番号(1)
ユーザー inu_hir0shi
提出日時 2015-07-10 23:27:04
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 4 ms
コード長 3,851 Byte
コンパイル時間 1,136 ms
使用メモリ 1,668 KB
最終ジャッジ日時 2019-10-13 05:48:59

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
99_system_test1.txt AC 3 ms
1,524 KB
99_system_test2.txt AC 4 ms
1,540 KB
99_system_test3.txt AC 3 ms
1,564 KB
99_system_test4.txt AC 3 ms
1,524 KB
99_system_test5.txt AC 4 ms
1,580 KB
99_system_test6.txt AC 3 ms
1,512 KB
99_system_test7.txt AC 4 ms
1,528 KB
99_system_test8.txt AC 3 ms
1,516 KB
challenge01.txt AC 3 ms
1,528 KB
challenge02.txt AC 3 ms
1,528 KB
sample1.txt AC 3 ms
1,528 KB
sample2.txt AC 3 ms
1,532 KB
sample3.txt AC 3 ms
1,528 KB
system_test1.txt AC 4 ms
1,560 KB
system_test2.txt AC 4 ms
1,664 KB
system_test3.txt AC 3 ms
1,652 KB
test1.txt AC 3 ms
1,524 KB
test2.txt AC 3 ms
1,516 KB
test3.txt AC 3 ms
1,524 KB
test4.txt AC 3 ms
1,528 KB
test5.txt AC 3 ms
1,524 KB
test6.txt AC 3 ms
1,524 KB
test7.txt AC 3 ms
1,524 KB
test8.txt AC 3 ms
1,584 KB
test9.txt AC 3 ms
1,660 KB
test10.txt AC 3 ms
1,664 KB
test11.txt AC 4 ms
1,660 KB
test12.txt AC 3 ms
1,664 KB
test13.txt AC 3 ms
1,660 KB
test14.txt AC 3 ms
1,660 KB
test15.txt AC 4 ms
1,668 KB
test16.txt AC 3 ms
1,664 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