Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cassert>
- #include <vector>
- #define ll long long
- #define mp make_pair
- #define pb push_back
- #define f first
- #define s second
- #define vi vector<int>
- #define vl vector<long long>
- #define sz(a) (int)((a).size())
- #define all(a) (a).begin(),(a).end()
- #define pii pair<int, int>
- #define pll pair<ll, ll>
- #define ld long double
- using namespace std;
- const int INF = 1e9;
- const int N = 200;
- const int M = 200;
- struct edge {
- int a, b, can;
- edge(int a, int b, int can) : a(a), b(b), can(can) { }
- };
- int n, m;
- int prob[M], team[N];
- int S, T;
- int q[N + M], d[N + M];
- int pt[N + M];
- vector < edge > edges;
- vector < int > g[N + M];
- char ans[N][M];
- void add_edge(int a, int b, int cap) {
- //cerr << a << " " << b << " " << cap << endl;
- g[a].pb(sz(edges));
- edges.pb( edge(a, b, cap) );
- g[b].pb(sz(edges));
- edges.pb( edge(b, a, 0) );
- //cerr << a << " " << b << " " << cap << endl;
- }
- bool bfs() {
- int ql = 0, qr = 0;
- q[qr++] = S;
- memset(d, -1, sizeof d);
- d[S] = 0;
- while(ql < qr) {
- int v = q[ql++];
- for(int id : g[v]) {
- int to = edges[id].b;
- if(d[to] == -1 && edges[id].can > 0) {
- d[to] = d[v] + 1;
- q[qr++] = to;
- }
- }
- }
- return d[T] != -1;
- }
- int dfs(int v, int flow) {
- if(flow == 0) return 0;
- if(v == T) return flow;
- for(; pt[v] < sz(g[v]); ++pt[v]) {
- int id = g[v][pt[v]];
- int to = edges[id].b;
- if(d[to] == d[v] + 1) {
- if(int pushed = dfs(to, min(flow, edges[id].can))) {
- edges[id].can -= pushed;
- edges[id ^ 1].can += pushed;
- return pushed;
- }
- }
- }
- return 0;
- }
- int dinic() {
- int flow = 0;
- while(bfs()) {
- memset(pt, 0, sizeof pt);
- while(int pushed = dfs(S, INF)) {
- flow += pushed;
- }
- }
- return flow;
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- int first = 1;
- while(cin >> n >> m && !(n == 0 && m == 0)) {
- if(!first) cout << "\n";
- first = 0;
- int sum1 = 0;
- for(int i = 1; i <= n; ++i) {
- cin >> team[i];
- sum1 += team[i];
- }
- int sum2 = 0;
- for(int i = 1; i <= m; ++i) {
- cin >> prob[i];
- sum2 += prob[i];
- }
- if(sum1 != sum2) {
- cout << "Impossible\n";
- continue;
- }
- for(int i = 0; i <= n + m + 1; ++i)
- g[i].clear();
- edges.clear();
- S = 0;
- for(int i = 1; i <= n; ++i)
- add_edge(S, i, team[i]);
- T = n + m + 1;
- for(int i = 1; i <= m; ++i)
- add_edge(n + i, T, prob[i]);
- for(int i = 1; i <= n; ++i)
- for(int j = m; j >= 1; --j)
- add_edge(i, n + j, 1);
- int max_flow = dinic();
- if(max_flow != sum1) {
- cout << "Impossible";
- } else {
- for(int i = 1; i <= n; ++i)
- for(int j = 1; j <= m; ++j)
- ans[i][j] = 'Y';
- for(int i = 1; i <= n; ++i) {
- for(int id : g[i]) {
- int j = edges[id].b;
- if(j == S || j == T) continue;
- bool flag = false;
- if(edges[id].can == 0) {
- add_edge(S, i, 1);
- add_edge(j, T, 1);
- edges[id].can = edges[id ^ 1].can = 0;
- if(dinic() > 0)
- flag = true;
- else {
- edges[sz(edges) - 4].can = 0;
- edges[sz(edges) - 3].can = 0;
- edges[sz(edges) - 2].can = 0;
- edges[sz(edges) - 1].can = 0;
- }
- } else {
- flag = true;
- }
- edges[id].can = edges[id ^ 1].can = 0;
- if(flag) cout << 'N';
- else cout << 'Y';
- }
- cout << "\n";
- }
- /*
- for(int i = 1; i <= n; ++i, cout << "\n")
- for(int j = 1; j <= m; ++j)
- cout << ans[i][j];
- */
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement