oj.uz

Submission #229505

# Submission time Handle Problem Language Result Execution time Memory
229505 2020-05-04T20:27:30 Z VEGAnn Konstrukcija (COCI20_konstrukcija) C++14
15 / 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) <= k)
        po++;

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

        mult(3);

        if ((1ll << po) & 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 5 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 5 ms 384 KB Correct.

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Wrong answer.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 5 ms 384 KB Correct.
6 Incorrect 5 ms 384 KB Wrong answer.
7 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 5 ms 384 KB Correct.
6 Incorrect 5 ms 384 KB Wrong answer.
7 Halted 0 ms 0 KB -