제출 #217620

#제출 시각아이디문제언어결과실행 시간메모리
217620LegoKonstrukcija (COCI20_konstrukcija)C++17
0 / 110
5 ms512 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; struct graf { int n; vector<pair<int, int>> edg; vector<int> back_l; graf(int _n, vector<pair<int, int>> edg_) { n = _n; edg = edg_; } graf() { n = 1; back_l.push_back(1); } int mylt_min_2(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 min_1(int pref) { edg.push_back({1, n + 1}); back_l.push_back(n + 1); n = n + 1; return pref - 1; } int mylt_min_1(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 zavrsi_isti() { vector<int> novi = {n + 1, n + 2}; for(auto x : back_l) for(auto y : novi) edg.push_back({x, y}); back_l = novi; for(auto x : back_l) edg.push_back({x, n + 3}); n = n + 3; } void zavrsi_minus() { for(auto x : back_l) edg.push_back({x, n + 1}); n = n + 1; } void print() { cout << n << ' ' << edg.size() << "\n"; for(auto p : edg) cout << p.first << ' ' << p.second << "\n"; } }; vector<int> powtwo(int t) { vector<int> ret; while(t > 0) { if(t & 1) ret.push_back(1); else ret.push_back(0); t /= 2; } reverse(ret.begin(), ret.end()); return ret; } void solve() { int k; cin >> k; int k_ = k; if(k == 0) { graf g(3, {{1, 2}, {2, 3}}); g.print(); return; } graf g; vector<int> binary; while(k_ > 0) { if(k_ & 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 = g.mylt_min_2(pref); if(binary[i]) { if(pref < 0) pref = g.mylt_min_1(pref); else pref = g.min_1(pref); } } assert(abs(k) == abs(pref)); if(pref == k) g.zavrsi_isti(); else g.zavrsi_minus(); g.print(); } 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...