oj.uz

Submission #988114

# Submission time Handle Problem Language Result Execution time Memory
988114 2024-05-24T05:06:39 Z vjudge1 Konstrukcija (COCI20_konstrukcija) C++17
110 / 110
 1 ms 600 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:10: 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 1 ms 344 KB Correct.
3 Correct 1 ms 596 KB Correct.
4 Correct 1 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 348 KB Correct.
2 Correct 1 ms 348 KB Correct.
3 Correct 1 ms 344 KB Correct.
4 Correct 1 ms 344 KB Correct.
5 Correct 1 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 1 ms 344 KB Correct.
3 Correct 1 ms 596 KB Correct.
4 Correct 1 ms 348 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 1 ms 348 KB Correct.
7 Correct 1 ms 348 KB Correct.
8 Correct 1 ms 344 KB Correct.
9 Correct 1 ms 344 KB Correct.
10 Correct 1 ms 348 KB Correct.
11 Correct 1 ms 348 KB Correct.
12 Correct 1 ms 348 KB Correct.
13 Correct 1 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 1 ms 344 KB Correct.
3 Correct 1 ms 596 KB Correct.
4 Correct 1 ms 348 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 1 ms 348 KB Correct.
7 Correct 1 ms 348 KB Correct.
8 Correct 1 ms 344 KB Correct.
9 Correct 1 ms 344 KB Correct.
10 Correct 1 ms 348 KB Correct.
11 Correct 1 ms 348 KB Correct.
12 Correct 1 ms 348 KB Correct.
13 Correct 1 ms 348 KB Correct.
14 Correct 1 ms 348 KB Correct.
15 Correct 1 ms 348 KB Correct.
16 Correct 1 ms 344 KB Correct.
17 Correct 1 ms 600 KB Correct.
18 Correct 1 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 348 KB Correct.
23 Correct 1 ms 348 KB Correct.
24 Correct 1 ms 432 KB Correct.
25 Correct 1 ms 348 KB Correct.
26 Correct 1 ms 544 KB Correct.
27 Correct 1 ms 348 KB Correct.