oj.uz

Submission #1091469

# Submission time Handle Problem Language Result Execution time Memory
1091469 2024-09-20T23:45:11 Z tfgs Konstrukcija (COCI20_konstrukcija) C++17
110 / 110
 1 ms 600 KB 
#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) {
        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};

    // 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;
    // };

 
    // vector<int> 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);


    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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct.
2 Correct 0 ms 348 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 0 ms 348 KB Correct.
5 Correct 0 ms 348 KB Correct.

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct.
2 Correct 0 ms 348 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 0 ms 348 KB Correct.
5 Correct 0 ms 348 KB Correct.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct.
2 Correct 0 ms 348 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 0 ms 348 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 1 ms 344 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 0 ms 348 KB Correct.
9 Correct 0 ms 348 KB Correct.
10 Correct 0 ms 348 KB Correct.
11 Correct 0 ms 348 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Correct 0 ms 348 KB Correct.
15 Correct 0 ms 348 KB Correct.

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct.
2 Correct 0 ms 348 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 0 ms 348 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 1 ms 344 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 0 ms 348 KB Correct.
9 Correct 0 ms 348 KB Correct.
10 Correct 0 ms 348 KB Correct.
11 Correct 0 ms 348 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Correct 0 ms 348 KB Correct.
15 Correct 0 ms 348 KB Correct.
16 Correct 1 ms 348 KB Correct.
17 Correct 1 ms 344 KB Correct.
18 Correct 1 ms 348 KB Correct.
19 Correct 0 ms 348 KB Correct.
20 Correct 1 ms 348 KB Correct.
21 Correct 0 ms 348 KB Correct.
22 Correct 1 ms 344 KB Correct.
23 Correct 0 ms 348 KB Correct.
24 Correct 0 ms 348 KB Correct.
25 Correct 0 ms 600 KB Correct.
26 Correct 0 ms 348 KB Correct.
27 Correct 0 ms 348 KB Correct.