제출 #217659

#제출 시각아이디문제언어결과실행 시간메모리
217659LegoKonstrukcija (COCI20_konstrukcija)C++17
110 / 110
5 ms384 KiB
#include <bits/stdc++.h> #define intl int #define int long long #define double long double const bool MULTI_TEST = false; const intl mod = 1e9 + 7, maxn = 400002, maxm = 2e5 + 1; using namespace std; int n = 1; vector<pair<int, int>> edg; vector<int> back_l = {1}; int mylt__ot2(int pref) { vector<int> new_ = {n + 1, n + 2, n + 3}; for (auto x : back_l) for (auto y : new_) edg.push_back({x, y}); back_l = new_; n = n + 3; return -2 * pref; } int otr(int pref) { edg.push_back({1, n + 1}); back_l.push_back(n + 1); n = n + 1; return pref - 1; } int pol(int pref) { vector<int> novi = {n + 1, n + 2}; for (auto x : back_l) for (auto y : novi) edg.push_back({x, y}); edg.push_back({1, n + 3}); novi.push_back(n + 3); back_l = novi; n = n + 3; return -pref - 1; } void solve() { int k; cin >> k; int k_ = abs(k); if (k == 0) { cout << "3 2\n1 2\n2 3"; return; } vector<int> binary; while (k_ > 0) { if (k_ % 2 == 1) binary.push_back(1); else binary.push_back(0); k_ /= 2; } reverse(binary.begin(), binary.end()); int pref = 1; for (int i = 1; i < (int) binary.size(); i++) { pref = mylt__ot2(pref); if (binary[i]) { if (pref < 0) pref = otr(pref); else pref = pol(pref); } } if (pref == k){ vector<int> new_l = {n + 1, n + 2}; for (auto x : back_l) for (auto y : new_l) edg.push_back({x, y}); back_l = new_l; for (auto x : back_l) edg.push_back({x, n + 3}); n = n + 3; } else{ for (auto x : back_l) edg.push_back({x, n + 1}); n = n + 1; } cout << n << ' ' << edg.size() << "\n"; for (auto p : edg) cout << p.first << ' ' << p.second << "\n"; } signed main() { //#ifdef _DEBUG // freopen("qual.in", "r", stdin);freopen("qual.out", "w", stdout); //#endif ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; if (MULTI_TEST) { std::cin >> t; } for (int i = 0; i < t; i++) { solve(); } 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...