Submission #229780

#	Time	Username	Problem	Language	Result	Execution time	Memory
229780		Vimmer	Konstrukcija (COCI20_konstrukcija)	C++14	110 / 110	6 ms	512 KiB

Main

#include <bits/stdc++.h>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) ll(x.size())
#define pb push_back
#define N 75005
#define M ll(1e9 + 7)


using namespace std;

typedef long double ld;
typedef long long ll;
typedef short int si;






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

    ll k, n = 1;

    cin >> k;

    if (k == 0)
    {
        cout << 3 << " " << 2 << endl << 1 << " " << 2 << endl << 2 << " " << 3 << endl;

        exit(0);
    }
    ll kk = abs(k);

    vector <pair <int, int> > ans; ans.clear();

    vector <int> lst; lst.clear();

    lst.pb(1);

    ll i = 0;

    while ((1ll << i) <= kk) i++;

    bool f = 1;

    i -= 2;

    while (i >= 0)
    {
        vector <int> cur; cur.clear();

        for (auto it : lst)
                {
                    for (int j = 1; j <= 3; j++)
                    {
                        n++;

                        ans.pb({it, n});
                    }

                    n -= 3;
                }

                for (int j = 1; j <= 3; j++) {n++; cur.pb(n);}

        f = !f;

        if ((1ll << i) & kk)
        {
            if (f)
            {
                lst = cur;

                cur.clear();

                f = !f;

                for (auto it : lst)
                {
                    for (int j = 1; j <= 2; j++)
                    {
                        n++;

                        ans.pb({it, n});
                    }

                    n -= 2;
                }

                for (int j = 1; j <= 2; j++) {n++; cur.pb(n);}
            }

            n++;

            ans.pb({1, n});

            cur.pb(n);
        }

        lst = cur;

        i--;
    }

    if (!f != (k > 0))
    {
        vector <int> cur; cur.clear();

        for (auto it : lst)
                {
                    for (int j = 1; j <= 2; j++)
                    {
                        n++;

                        ans.pb({it, n});
                    }

                    n -= 2;
                }

                for (int j = 1; j <= 2; j++) {n++; cur.pb(n);}

        lst = cur;
    }

    n++;

    for (auto it : lst) ans.pb({it, n});

    cout << n << " " << sz(ans) << '\n';

    for (auto it : ans) cout << it.F << " " << it.S << '\n';
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 60 / 60