oj.uz

Submission #229506

# Submission time Handle Problem Language Result Execution time Memory
229506 2020-05-04T20:30:36 Z VEGAnn Konstrukcija (COCI20_konstrukcija) C++14
110 / 110
 5 ms 384 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define pii pair<int,int>
#define MP make_pair
#define ft first
#define sd second
using namespace std;
typedef long long ll;
vector<pii> vc;
vector<int> layer, new_layer;
ll k;
int lst;
bool pos;

void mult(int x){
    new_layer.clear();
    for (int it = 0; it < x; it++)
        new_layer.PB(++lst);

    pos ^= 1;

    for (int fi : layer)
        for (int se : new_layer)
            vc.PB(MP(fi, se));

    layer = new_layer;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> k;

    if (k == 0){
        cout << "3 2\n1 2\n2 3";
        return 0;
    }

    layer.clear();
    layer.PB(1);
    lst = 1;

    pos = 1;

    ll po = 0;

    while ((1ll << po) <= abs(k))
        po++;

    for (po -= 2; ; po--){
        if (po < 0) break;

        mult(3);

        if ((1ll << po) & abs(k)) {
            if (pos) mult(2);
            vc.PB(MP(1, ++lst));
            layer.PB(lst);
        }
    }

    bool pos_val = bool(k > 0);

    if (pos == pos_val)
        mult(2);

    ++lst;

    for (int fi : layer)
        vc.PB(MP(fi, lst));

    cout << lst << " " << sz(vc) << '\n';

    for (pii cr : vc)
        cout << cr.ft << " " << cr.sd << '\n';

    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
60.0 / 60.0

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