oj.uz

Submission #229780

# Submission time Handle Problem Language Result Execution time Memory
229780 2020-05-06T11:05:04 Z Vimmer Konstrukcija (COCI20_konstrukcija) C++14
110 / 110
 6 ms 512 KB 
#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.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 4 ms 384 KB Correct.
4 Correct 4 ms 384 KB Correct.
5 Correct 5 ms 384 KB Correct.

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 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 5 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 4 ms 384 KB Correct.
4 Correct 4 ms 384 KB Correct.
5 Correct 5 ms 384 KB Correct.
6 Correct 6 ms 384 KB Correct.
7 Correct 4 ms 384 KB Correct.
8 Correct 5 ms 384 KB Correct.
9 Correct 4 ms 384 KB Correct.
10 Correct 5 ms 384 KB Correct.
11 Correct 5 ms 384 KB Correct.
12 Correct 4 ms 384 KB Correct.
13 Correct 5 ms 384 KB Correct.
14 Correct 4 ms 384 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 4 ms 384 KB Correct.
4 Correct 4 ms 384 KB Correct.
5 Correct 5 ms 384 KB Correct.
6 Correct 6 ms 384 KB Correct.
7 Correct 4 ms 384 KB Correct.
8 Correct 5 ms 384 KB Correct.
9 Correct 4 ms 384 KB Correct.
10 Correct 5 ms 384 KB Correct.
11 Correct 5 ms 384 KB Correct.
12 Correct 4 ms 384 KB Correct.
13 Correct 5 ms 384 KB Correct.
14 Correct 4 ms 384 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 512 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.