oj.uz

Submission #238734

# Submission time Handle Problem Language Result Execution time Memory
238734 2020-06-12T12:57:56 Z SamAnd Konstrukcija (COCI20_konstrukcija) C++17
110 / 110
 7 ms 640 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 1003;

struct stg0
{
    int n, m;
    vector<int> a[N];

    vector<int> v;
    bool cc[N];
    void dfs1(int x)
    {
        cc[x] = true;
        v.push_back(x);
        for (int i = 0; i < a[x].size(); ++i)
        {
            int h = a[x][i];
            if (!cc[h])
                dfs1(h);
        }
    }

    bool c[N];
    int k[N], z[N];
    void dfs(int x)
    {
        c[x] = true;
        if (x == n)
        {
            k[x] = 1;
            return;
        }
        v.clear();
        memset(cc, 0, sizeof cc);
        dfs1(x);
        vector<int> yv = v;
        for (int i = 0; i < yv.size(); ++i)
        {
            int h = yv[i];
            if (h == x)
                continue;
            if (!c[h])
                dfs(h);
            z[x] += k[h];
            k[x] += z[h];
        }
        printf("%d %d\n", x, k[x] - z[x]);
    }

    void por()
    {
        /*scanf("%d", &n);
        int x, y;
        while (scanf("%d%d", &x, &y) != EOF)
        {
            a[x].push_back(y);
        }*/
        scanf("%d%d", &n, &m);
        while (m--)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            a[x].push_back(y);
        }
        dfs(1);
        printf("%d\n", k[1] - z[1]);
    }
};

int n;
vector<pair<int, int> > ans;

ll k;

vector<int> v;

void ave(int x)
{
    k *= -(x - 1);
    vector<int> u;
    for (int i = 0; i < x; ++i)
        u.push_back(--n);
    for (int i1 = 0; i1 < v.size(); ++i1)
    {
        for (int i2 = 0; i2 < u.size(); ++i2)
        {
            ans.push_back(m_p(u[i2], v[i1]));
        }
    }
    v = u;
}

void solv()
{
    scanf("%lld", &k);
    if (k == 0)
    {
        printf("6 6\n");
        printf("1 4\n");
        printf("1 5\n");
        printf("4 3\n");
        printf("5 3\n");
        printf("3 2\n");
        printf("2 6\n");
        return;
    }
    bool z = false;
    if (k < 0)
    {
        z = true;
        k *= -1;
    }
    vector<int> bk;
    while (k)
    {
        bk.push_back(k % 2);
        k /= 2;
    }
    reverse(all(bk));
    k = 1;
    n = 1001;
    v.push_back(--n);
    ave(2);
    for (int i = 1; i < bk.size(); ++i)
    {
        ave(3);
        if (bk[i])
        {
            if (k > 0)
                ave(2);
            v.push_back(--n);
            ans.push_back(m_p(v.back(), 1000));
            --k;
        }
    }
    if ((k > 0 && !z) || (k < 0 && z))
        ave(2);
    for (int i = 0; i < v.size(); ++i)
        ans.push_back(m_p(1, v[i]));
    printf("%d %d\n", 1000, ans.size());
    for (int i = 0; i < ans.size(); ++i)
        printf("%d %d\n", ans[i].fi, ans[i].se);
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    //ios_base::sync_with_stdio(false), cin.tie(0);
    //stg0().por();
    //return 0;
    solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

Compilation message

konstrukcija.cpp: In member function 'void stg0::dfs1(int)':
konstrukcija.cpp:24:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < a[x].size(); ++i)
                         ~~^~~~~~~~~~~~~
konstrukcija.cpp: In member function 'void stg0::dfs(int)':
konstrukcija.cpp:46:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < yv.size(); ++i)
                         ~~^~~~~~~~~~~
konstrukcija.cpp: In function 'void ave(int)':
konstrukcija.cpp:92:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i1 = 0; i1 < v.size(); ++i1)
                      ~~~^~~~~~~~~~
konstrukcija.cpp:94:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i2 = 0; i2 < u.size(); ++i2)
                          ~~~^~~~~~~~~~
konstrukcija.cpp: In function 'void solv()':
konstrukcija.cpp:133:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < bk.size(); ++i)
                     ~~^~~~~~~~~~~
konstrukcija.cpp:147:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~
konstrukcija.cpp:149:39: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d %d\n", 1000, ans.size());
                             ~~~~~~~~~~^
konstrukcija.cpp:150:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < ans.size(); ++i)
                     ~~^~~~~~~~~~~~
konstrukcija.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &k);
     ~~~~~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Correct.
2 Correct 7 ms 640 KB Correct.
3 Correct 5 ms 384 KB Correct.
4 Correct 5 ms 384 KB Correct.
5 Correct 6 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 6 ms 384 KB Correct.
3 Correct 5 ms 308 KB Correct.
4 Correct 6 ms 384 KB Correct.
5 Correct 6 ms 384 KB Correct.

Subtask #3
20.0 / 20.0

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

Subtask #4
60.0 / 60.0

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