oj.uz

Submission #1091463

# Submission time Handle Problem Language Result Execution time Memory
1091463 2024-09-20T23:37:25 Z tfgs Konstrukcija (COCI20_konstrukcija) C++17
110 / 110
 1 ms 516 KB 
    #include <bits/stdc++.h>
    using namespace std;
     
    using ll  = long long;
    using pii = pair<int, int>;
     
    #define fi first
    #define se second
     
    const int maxN  = 1'023;
     
    ll K;
    bool neg = false;
    int N, M;
    vector<pii> edges;
     
    int main() {
        scanf("%lld", &K);
        if (K == 0) {
            printf("3 2\n");
            printf("1 2\n");
            printf("2 3\n");
            exit(0);
        }
     
        edges.push_back({1, 2});
        edges.push_back({1, 3});
        vector<int> lst = {2, 3};
     
        if (K < 0) {
            neg = true;
            K *= -1;
        }
        vector<int> bt;
        while (K > 1) {
            if (K & 1ll) bt.push_back(1);
            bt.push_back(2);
            K >>= 1;
        }
        reverse(bt.begin(), bt.end());
     
        auto convolve = [&](int k) {
            vector<int> nw(k);
            iota(nw.begin(), nw.end(), N+1);
            N += k;
            for (auto i : lst) {
                for (auto j : nw) {
                    edges.push_back({i, j});
                }
            }        
            swap(lst, nw);
        };
     
        N = 3;
        for (auto i : bt) {
            if (i == 1) {
                // add 1
                N++;
                edges.push_back({1, N});
                lst.push_back(N);
            } else {
                // multiply by 2
                convolve(3);
                convolve(2);
            }
        }
     
        if (neg) convolve(2);
     
        N++;
        for (auto i : lst) edges.push_back({i, N});
     
        M = edges.size();
     
        printf("%d %d\n", N, M);
        for (auto [u, v] : edges) {
            printf("%d %d\n", u, v);
        }
    }

Compilation message

konstrukcija.cpp: In function 'int main()':
konstrukcija.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf("%lld", &K);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
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 #2
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 #3
20.0 / 20.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.
6 Correct 0 ms 348 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 1 ms 348 KB Correct.
12 Correct 1 ms 348 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Correct 1 ms 348 KB Correct.
15 Correct 1 ms 348 KB Correct.

Subtask #4
60.0 / 60.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.
6 Correct 0 ms 348 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 1 ms 348 KB Correct.
12 Correct 1 ms 348 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Correct 1 ms 348 KB Correct.
15 Correct 1 ms 348 KB Correct.
16 Correct 0 ms 348 KB Correct.
17 Correct 0 ms 516 KB Correct.
18 Correct 0 ms 348 KB Correct.
19 Correct 1 ms 348 KB Correct.
20 Correct 1 ms 348 KB Correct.
21 Correct 1 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 348 KB Correct.
26 Correct 1 ms 348 KB Correct.
27 Correct 0 ms 348 KB Correct.