Submission #636757

#TimeUsernameProblemLanguageResultExecution timeMemory
636757nguyen31hoang08minh2003Sob (COCI19_sob)C++14
49 / 110
38 ms3784 KiB
/* \|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/ \\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||// /-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\ \--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/ /---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\ \---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/ /--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\ \-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/ //||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\ /|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\ \|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/\|\//\\//\\/|/ \\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||//\\||\//\\/||// /-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\/-\|||\/|||/-\ \--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/\--\||/\||/--/ /---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\/---\//\\/---\ \---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/\---/\\//\---/ /--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\/--/||\/||\--\ \-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/\-/|||/\|||\-/ //||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\//||/\\//\||\\ /|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\/|/\\//\\//\|\ */ #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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...