fork download

#include <bits/stdc++.h>
using namespace std;
int n, m;
int cost[1205][1205];
 
// Use:
// Constructor: Dinic dinic(n)
// 
// add edges: dinic.addEdge(u, v, c)
// 
// trace: for (auto e: dinic.E) {
//  if (e.flow && e.cap) {
//      cout << e.u << " " << e.v << " " << e.flow << endl;
//  }
// }
// 
// minCut: i from (0 to dinic.N - 1): dinic.d[i] != dinic.N + 1
struct Edge {
    int u, v;
    long long cap, flow;
    Edge() {}
    Edge(int u, int v, long long cap): u(u), v(v), cap(cap), flow(0) {}
};
 
struct Dinic {
    int N;
    vector<Edge> E;
    vector<vector<int>> g;
    vector<int> d, pt;
    Dinic(int N): N(N), E(0), g(N), d(N), pt(N) {}
    void addEdge(int u, int v, long long cap) {
        if (u != v) {
            E.emplace_back(Edge(u, v, cap));
            g[u].emplace_back(E.size() - 1);
            E.emplace_back(Edge(v, u, 0));
            g[v].emplace_back(E.size() - 1);
        }
    }
    bool bfs(int S, int T) {
        queue<int> q({S});
        fill(d.begin(), d.end(), N + 1);
        d[S] = 0;
        while(!q.empty()) {
            int u = q.front(); q.pop();
            if (u == T) break;
            for (int k: g[u]) {
                Edge &e = E[k];
                if (e.flow < e.cap && d[e.v] > d[e.u] + 1) {
                    d[e.v] = d[e.u] + 1;
                    q.emplace(e.v);
                }
            }
        }
        return d[T] != N + 1;
    }
    long long dfs(int u, int T, long long flow = -1) {
        if (u == T || flow == 0) return flow;
        for (int &i = pt[u]; i < g[u].size(); ++i) {
            Edge &e = E[g[u][i]];
            Edge &oe = E[g[u][i]^1];
            if (d[e.v] == d[e.u] + 1) {
                long long amt = e.cap - e.flow;
                if (flow != -1 && amt > flow) amt = flow;
                if (long long pushed = dfs(e.v, T, amt)) {
                    e.flow += pushed;
                    oe.flow -= pushed;
                    return pushed;
                }
            }
        }
        return 0;
    }
    long long maxFlow(int S, int T) {
        long long total = 0;
        while (bfs(S, T)) {
            fill(pt.begin(), pt.end(), 0);
            while (long long flow = dfs(S, T))
                total += flow;
        }
        return total;
    }
};
 
 
void sub3() {
    vector<int> match(n + 1);
 
    auto solve = [&](int x) {
        int source = 0;
        int sink = n + m + 1;
        Dinic dinic(sink + 1);
 
        for (int i = 1; i <= n; i++) {
            dinic.addEdge(source, i, 1);
        }
 
        for (int i = 1; i <= m; i++) {
            dinic.addEdge(i + n, sink, 1);
        }
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (cost[i][j] >= x) {
                    dinic.addEdge(i, j + n, 1);
                } 
            }
        }
 
 
        if (dinic.maxFlow(source, sink) == n) {
            for (auto e: dinic.E) {
                if (e.flow && e.cap) {
                    if (e.u > 0 && e.u <= n) {
                        match[e.u] = e.v - n;
                    }
                }
            }
            return 1;
        }
        return 0;
    };
 
    int lower = 1, upper = 2000;
    while (lower < upper) {
        int mid = (lower + upper + 1) / 2;
        if (solve(mid)) {
            lower = mid;
        }
        else {
            upper = mid - 1;
        }
    }
    solve(lower);
    for (int i = 1; i <= n; i++) {
        cout << 1 << " " << match[i] << "\n";
    }
}
 
struct Sub1 {
    int dp[15][1 << 12];
    int trace[15][1 << 12];
    Sub1() {
        memset(dp, 0, sizeof(dp));
        memset(trace, -1, sizeof(trace));
    }
 
    void solve() {
        dp[0][0] = 1e9;
        for (int i = 1; i <= n; i++) {
            for (int bit = 0; bit < (1 << m); bit++) {
                for (int curBit = 1; curBit < (1 << m); curBit++) {
                    if (bit & (curBit)) continue;
 
 
                    int newBit = bit | curBit;
 
                    int curVal = 0;
                    for (int j = 1; j <= m; j++) {
                        if (curBit & (1 << (j - 1))) {
                            curVal += cost[i][j];
                        }
                    }
 
                    int newVal = min(dp[i - 1][bit], curVal);
 
                    if (newVal > dp[i][newBit]) {
                        dp[i][newBit] = newVal;
                        trace[i][newBit] = curBit;
                    }
                }
            }
        }
 
        int curBit = (1 << m) - 1;
        vector<vector<int>> res;
        for (int i = n; i >= 1; i--) {
            int bit = trace[i][curBit];
            curBit -= bit;
 
            vector<int> cur;
            for (int j = 0; j < m; j++) {
                if (bit & (1 << j)) {
                    cur.push_back(j + 1);
                }
            }
            res.push_back(cur);
        }
        reverse(res.begin(), res.end());
        for (auto &v: res) {
            cout << v.size() << " ";
            for (auto i: v) cout << i << " ";
            cout << "\n";
        }
    }
};
 
struct Data {
    int first, second, index;
};
 
void sub2() {
    vector<Data> v;
 
    int sumAllB = 0;
    for (int i = 1; i <= m; i++) {
        v.push_back({cost[1][i], cost[2][i], i});
        sumAllB += cost[2][i];
    }
    sort(v.begin(), v.end(), [](Data a, Data b) {
        return a.first - a.second > b.first - b.second;
    });
 
    vector<int> resA, resB;
    int finalRes = 0;
 
    for (int z = 0; z <= 50000; z++) {
 
        if (z) {
            for (int i = 0; i + 1 < v.size(); i++) {
                if (rand() % (z / 100 + 2) == 0) swap(v[i], v[i + 1]); 
            }
        }
        int sumB = sumAllB;
        int res = 0, sumA = 0;
        int index = -1;
        for (int i = 0; i < m; i++) {
            sumA += v[i].first;
            sumB -= v[i].second;
            if (res < min(sumA, sumB)) {
                res = min(sumA, sumB);
                index = i;
            }
        }
        vector<int> tmpA, tmpB;
        for (int i = 0; i < m; i++) {
            if (i <= index) {
                tmpA.push_back(v[i].index);
            }
            else {
                tmpB.push_back(v[i].index);
            }
        }
 
        if (res > finalRes) {
            resA = tmpA;
            resB = tmpB;
            finalRes = res;
        }
    }
 
    sort(resA.begin(), resA.end());
    sort(resB.begin(), resB.end());
 
    cout << resA.size() << " ";
    for (auto i: resA) cout << i << " "; 
    cout << "\n";
 
    cout << resB.size() << " ";
    for (auto i: resB) cout << i << " ";
    cout << "\n";
}
 
int main() {
    srand(time(0));
    // freopen("input.txt", "r", stdin);
    // freopen("bonus.inp", "r", stdin);
    // freopen("bonus.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
 
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> cost[i][j];
        }
    }
 
    if (m <= 12 && n <= 12) {
        Sub1().solve();
    }
    else if (m == n) {
        sub3();
    }
    else {
        sub2();
    }
 
 
 
    return 0;
}
 

Main.java:1: error: illegal character: '#'
#include <bits/stdc++.h>
^
Main.java:1: error: class, interface, or enum expected
#include <bits/stdc++.h>
         ^
Main.java:3: error: class, interface, or enum expected
int n, m;
^
Main.java:4: error: class, interface, or enum expected
int cost[1205][1205];
^
Main.java:18: error: class, interface, or enum expected
struct Edge {
^
Main.java:20: error: class, interface, or enum expected
    long long cap, flow;
    ^
Main.java:21: error: class, interface, or enum expected
    Edge() {}
    ^
Main.java:25: error: class, interface, or enum expected
struct Dinic {
^
Main.java:27: error: class, interface, or enum expected
    vector<Edge> E;
    ^
Main.java:28: error: class, interface, or enum expected
    vector<vector<int>> g;
    ^
Main.java:29: error: class, interface, or enum expected
    vector<int> d, pt;
    ^
Main.java:30: error: class, interface, or enum expected
    Dinic(int N): N(N), E(0), g(N), d(N), pt(N) {}
    ^
Main.java:34: error: class, interface, or enum expected
            g[u].emplace_back(E.size() - 1);
            ^
Main.java:35: error: class, interface, or enum expected
            E.emplace_back(Edge(v, u, 0));
            ^
Main.java:36: error: class, interface, or enum expected
            g[v].emplace_back(E.size() - 1);
            ^
Main.java:37: error: class, interface, or enum expected
        }
        ^
Main.java:41: error: class, interface, or enum expected
        fill(d.begin(), d.end(), N + 1);
        ^
Main.java:42: error: class, interface, or enum expected
        d[S] = 0;
        ^
Main.java:43: error: class, interface, or enum expected
        while(!q.empty()) {
        ^
Main.java:44: error: class, interface, or enum expected
            int u = q.front(); q.pop();
                               ^
Main.java:45: error: class, interface, or enum expected
            if (u == T) break;
            ^
Main.java:46: error: class, interface, or enum expected
            for (int k: g[u]) {
            ^
Main.java:48: error: class, interface, or enum expected
                if (e.flow < e.cap && d[e.v] > d[e.u] + 1) {
                ^
Main.java:50: error: class, interface, or enum expected
                    q.emplace(e.v);
                    ^
Main.java:51: error: class, interface, or enum expected
                }
                ^
Main.java:55: error: class, interface, or enum expected
    }
    ^
Main.java:58: error: class, interface, or enum expected
        for (int &i = pt[u]; i < g[u].size(); ++i) {
        ^
Main.java:58: error: class, interface, or enum expected
        for (int &i = pt[u]; i < g[u].size(); ++i) {
                             ^
Main.java:58: error: class, interface, or enum expected
        for (int &i = pt[u]; i < g[u].size(); ++i) {
                                              ^
Main.java:60: error: class, interface, or enum expected
            Edge &oe = E[g[u][i]^1];
            ^
Main.java:61: error: class, interface, or enum expected
            if (d[e.v] == d[e.u] + 1) {
            ^
Main.java:63: error: class, interface, or enum expected
                if (flow != -1 && amt > flow) amt = flow;
                ^
Main.java:64: error: class, interface, or enum expected
                if (long long pushed = dfs(e.v, T, amt)) {
                ^
Main.java:66: error: class, interface, or enum expected
                    oe.flow -= pushed;
                    ^
Main.java:67: error: class, interface, or enum expected
                    return pushed;
                    ^
Main.java:68: error: class, interface, or enum expected
                }
                ^
Main.java:72: error: class, interface, or enum expected
    }
    ^
Main.java:75: error: class, interface, or enum expected
        while (bfs(S, T)) {
        ^
Main.java:77: error: class, interface, or enum expected
            while (long long flow = dfs(S, T))
            ^
Main.java:79: error: class, interface, or enum expected
        }
        ^
Main.java:81: error: class, interface, or enum expected
    }
    ^
Main.java:85: error: class, interface, or enum expected
void sub3() {
^
Main.java:88: error: class, interface, or enum expected
    auto solve = [&](int x) {
    ^
Main.java:90: error: class, interface, or enum expected
        int sink = n + m + 1;
        ^
Main.java:91: error: class, interface, or enum expected
        Dinic dinic(sink + 1);
        ^
Main.java:93: error: class, interface, or enum expected
        for (int i = 1; i <= n; i++) {
        ^
Main.java:93: error: class, interface, or enum expected
        for (int i = 1; i <= n; i++) {
                        ^
Main.java:93: error: class, interface, or enum expected
        for (int i = 1; i <= n; i++) {
                                ^
Main.java:95: error: class, interface, or enum expected
        }
        ^
Main.java:97: error: class, interface, or enum expected
        for (int i = 1; i <= m; i++) {
                        ^
Main.java:97: error: class, interface, or enum expected
        for (int i = 1; i <= m; i++) {
                                ^
Main.java:99: error: class, interface, or enum expected
        }
        ^
Main.java:101: error: class, interface, or enum expected
        for (int i = 1; i <= n; i++) {
                        ^
Main.java:101: error: class, interface, or enum expected
        for (int i = 1; i <= n; i++) {
                                ^
Main.java:102: error: class, interface, or enum expected
            for (int j = 1; j <= m; j++) {
                            ^
Main.java:102: error: class, interface, or enum expected
            for (int j = 1; j <= m; j++) {
                                    ^
Main.java:105: error: class, interface, or enum expected
                } 
                ^
Main.java:115: error: class, interface, or enum expected
                    }
                    ^
Main.java:119: error: class, interface, or enum expected
        }
        ^
Main.java:121: error: class, interface, or enum expected
    };
    ^
Main.java:123: error: class, interface, or enum expected
    int lower = 1, upper = 2000;
    ^
Main.java:124: error: class, interface, or enum expected
    while (lower < upper) {
    ^
Main.java:126: error: class, interface, or enum expected
        if (solve(mid)) {
        ^
Main.java:128: error: class, interface, or enum expected
        }
        ^
Main.java:131: error: class, interface, or enum expected
        }
        ^
Main.java:134: error: class, interface, or enum expected
    for (int i = 1; i <= n; i++) {
    ^
Main.java:134: error: class, interface, or enum expected
    for (int i = 1; i <= n; i++) {
                    ^
Main.java:134: error: class, interface, or enum expected
    for (int i = 1; i <= n; i++) {
                            ^
Main.java:136: error: class, interface, or enum expected
    }
    ^
Main.java:141: error: class, interface, or enum expected
    int trace[15][1 << 12];
    ^
Main.java:142: error: class, interface, or enum expected
    Sub1() {
    ^
Main.java:144: error: class, interface, or enum expected
        memset(trace, -1, sizeof(trace));
        ^
Main.java:145: error: class, interface, or enum expected
    }
    ^
Main.java:149: error: class, interface, or enum expected
        for (int i = 1; i <= n; i++) {
        ^
Main.java:149: error: class, interface, or enum expected
        for (int i = 1; i <= n; i++) {
                        ^
Main.java:149: error: class, interface, or enum expected
        for (int i = 1; i <= n; i++) {
                                ^
Main.java:150: error: class, interface, or enum expected
            for (int bit = 0; bit < (1 << m); bit++) {
                              ^
Main.java:150: error: class, interface, or enum expected
            for (int bit = 0; bit < (1 << m); bit++) {
                                              ^
Main.java:151: error: class, interface, or enum expected
                for (int curBit = 1; curBit < (1 << m); curBit++) {
                                     ^
Main.java:151: error: class, interface, or enum expected
                for (int curBit = 1; curBit < (1 << m); curBit++) {
                                                        ^
Main.java:155: error: class, interface, or enum expected
                    int newBit = bit | curBit;
                    ^
Main.java:157: error: class, interface, or enum expected
                    int curVal = 0;
                    ^
Main.java:158: error: class, interface, or enum expected
                    for (int j = 1; j <= m; j++) {
                    ^
Main.java:158: error: class, interface, or enum expected
                    for (int j = 1; j <= m; j++) {
                                    ^
Main.java:158: error: class, interface, or enum expected
                    for (int j = 1; j <= m; j++) {
                                            ^
Main.java:161: error: class, interface, or enum expected
                        }
                        ^
Main.java:166: error: class, interface, or enum expected
                    if (newVal > dp[i][newBit]) {
                    ^
Main.java:168: error: class, interface, or enum expected
                        trace[i][newBit] = curBit;
                        ^
Main.java:169: error: class, interface, or enum expected
                    }
                    ^
Main.java:175: error: class, interface, or enum expected
        vector<vector<int>> res;
        ^
Main.java:176: error: class, interface, or enum expected
        for (int i = n; i >= 1; i--) {
        ^
Main.java:176: error: class, interface, or enum expected
        for (int i = n; i >= 1; i--) {
                        ^
Main.java:176: error: class, interface, or enum expected
        for (int i = n; i >= 1; i--) {
                                ^
Main.java:178: error: class, interface, or enum expected
            curBit -= bit;
            ^
Main.java:180: error: class, interface, or enum expected
            vector<int> cur;
            ^
Main.java:181: error: class, interface, or enum expected
            for (int j = 0; j < m; j++) {
            ^
Main.java:181: error: class, interface, or enum expected
            for (int j = 0; j < m; j++) {
                            ^
Main.java:181: error: class, interface, or enum expected
            for (int j = 0; j < m; j++) {
                                   ^
Main.java:184: error: class, interface, or enum expected
                }
                ^
Main.java:187: error: class, interface, or enum expected
        }
        ^
100 errors

Standard output is empty