Submission #229506

#	Time	Username	Problem	Language	Result	Execution time	Memory
229506		VEGAnn	Konstrukcija (COCI20_konstrukcija)	C++14	110 / 110	5 ms	384 KiB

Main

#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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 60 / 60