oj.uz

Submission #636757

# Submission time Handle Problem Language Result Execution time Memory
636757 2022-08-30T03:39:28 Z nguyen31hoang08minh2003 Sob (COCI19_sob) C++14
49 / 110
 38 ms 3784 KB 
/*
\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/
\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//
/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\
\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/
/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\
\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/
/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\
\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/
//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\
/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\
\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/
\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//
/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\
\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/
/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\
\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/
/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\
\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/
//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\
/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\
*/
#include <bits/stdc++.h>
#define fore(i, a, b) for (signed i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (signed i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (signed i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

void subtask1(int n, int m) {
/*

    For numbers from m to (m + n - 1), if we "ignore" (or "remove") the k-th digits (in binary base) (k >= n),
    these numbers would create a "cycle" with numbers from 0 to n - 1

*/
    fore(y, m, m + n) {
        cout << ((n - 1) & y) << ' ' << y << '\n';
    }
}

bool checkPowerOfTwo(int x) {
    return !(x & (x - 1));
}

void subtask3(int n, int m) {
/*

    Construct bipartite graph and find maximum matching

*/
    const function<bool(int, int)> checkConnected = [&](const int x, const int y) -> bool {
        return (x & y) == x;
    };
    vvi adj(n);
    vi matchX(n, -1), matchY(n, -1), trace(n, -1);
    vector<bool> vis(n);
    const function<int(void)> bfs = [&]() -> int {
        queue<int> q;
        fore(i, 0, n) {
            trace[i] = -1;
            if(matchX[i] < 0){
                q.push(i);
                vis[i] = true;
            } else
                vis[i] = false;
        }
        for (; !q.empty(); q.pop()) {
            const int &ux = q.front();
            for (const int &uy : adj[ux])
                if (trace[uy] < 0){
                    trace[uy] = ux;
                    if (matchY[uy] < 0)
                        return uy;
                    if (!vis[matchY[uy]]) {
                        vis[matchY[uy]] = true;
                        q.push(matchY[uy]);
                    }
                }
        }
        return -1;
    };
    const function<void(int)> enlarge = [&](int u) {
        for (int v, nxt; u >= 0;){
            v = trace[u];
            nxt = matchX[v];
            matchY[u] = v;
            matchX[v] = u;
            u = nxt;
        }
    };
    fore(x, 0, n)
        fore(y, 0, n)
            if (checkConnected(x, y + m))
                adj[x].pb(y);
    for (int u; (u = bfs()) >= 0;)
        enlarge(u);
//    fore(x, 0, n)
//        cerr << x << ' ' << matchX[x] << ' ' << adj[x].size() << '\n';
    fore(x, 0, n)
        cout << x << ' ' << matchX[x] + m << '\n';
}

int main() {
    int n, m;
    #ifdef LOCAL
        freopen("input.INP", "r", stdin);
//        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    if (checkPowerOfTwo(n))
        subtask1(n, m);
    else if (n <= 1000 && m <= 1000)
        subtask3(n, m);
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 38 ms 3784 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 38 ms 3784 KB Output is correct
5 Incorrect 0 ms 212 KB Unexpected end of file - int32 expected
6 Halted 0 ms 0 KB -