제출 #1091467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1091467		tfgs	Konstrukcija (COCI20_konstrukcija)	C++17	110 / 110	1 ms	600 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int int64_t

#ifdef LOCAL
#include "algo/debug.h"
#endif

#define f first
#define s second
template<class T> using V = vector<T>; 
using vi = V<int>;
using vb = V<bool>;
using vs = V<string>;

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x) 
#define len(x) (int)((x).size())
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define lb lower_bound
#define ub upper_bound
template<class T> int lwb(V<T>& a, const T& b) { return lb(all(a),b)-begin(a); }
template<class T> int upb(V<T>& a, const T& b) { return ub(all(a),b)-begin(a); }
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a=b, true : false; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a=b, true : false; }
#define pct __builtin_popcount
#define ctz __builtin_ctz
#define clz __builtin_clz
constexpr int p2(int x) { return (int)1 << x; }
constexpr int bits(int x) { return x == 0 ? 0 : 31-clz(x); } // floor(log2(x)) 

const int LOG = 64;

void solve() {
    int k; cin >> k; 
    if (!k) {
        // cout << "1 0\n";
        printf("3 2\n");
        printf("1 2\n");
        printf("2 3\n");
        return;
    }
    bool neg = false;
    if (k < 0) {
        neg = true;
        k = -k;
    }
    
    int n = 3;
    V<array<int, 2>> edges;

    // vi lst = {2, 3};
    // edges.pb({1, 2});
    // edges.pb({1, 3});
    // auto append = [&](int k) {
        // vi nw(k);
        // iota(all(nw), n+1);
        // for (int i = 0; i < len(lst); i++) {
            // for (int j = 0; j < len(nw); j++) {
                // edges.pb({lst[i], nw[j]});
            // }
        // }
        // swap(nw, lst);
        // n += k;
    // };

    // vi events;
    // while (k > 1) {
        // if (k%2) events.pb(1);
        // events.pb(2);
        // k /= 2;
    // }
    // reverse(all(events));
    // for (int event : events) {
        // if (event == 1) {
            // // add 1
            // edges.pb({1, ++n});
            // lst.pb(n);
        // } else {
            // // multiply by 2
            // append(3);
            // append(2);
        // }
    // }
    // if (neg) append(2);

    edges.push_back({1, 2});
    edges.push_back({1, 3});
    vector<int> lst = {2, 3};
 
    // if (k < 0) {
        // neg = true;
        // k *= -1;
    // }
    vector<int> events;
    // while (k > 1) {
        // if (k & 1ll) events.push_back(1);
        // events.push_back(2);
        // k >>= 1;
    // }
    // reverse(events.begin(), events.end());
    while (k > 1) {
        if (k%2) events.pb(1);
        events.pb(2);
        k /= 2;
    }
    reverse(all(events));


    auto append = [&](int k) {
        vi nw(k);
        iota(all(nw), n+1);
        for (int i = 0; i < len(lst); i++) {
            for (int j = 0; j < len(nw); j++) {
                edges.pb({lst[i], nw[j]});
            }
        }
        swap(nw, lst);
        n += k;
    };

    for (int event : events) {
        if (event == 1) {
            // add 1
            edges.pb({1, ++n});
            lst.pb(n);
        } else {
            // multiply by 2
            append(3);
            append(2);
        }
    }
    if (neg) append(2);


    n++;
    for (int u : lst) edges.pb({u, n});
    int m = len(edges);
    cout << n << ' ' << m << '\n';
    for (auto [u, v] : edges) cout << u << ' ' << v << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 60 / 60