oj.uz

Submission #249530

# Submission time Handle Problem Language Result Execution time Memory
249530 2020-07-15T08:15:10 Z Vimmer Poklon (COCI17_poklon7) C++14
120 / 120
 810 ms 182640 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#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) int(x.size())
#define pb push_back
#define pf push_front
#define N 1000010
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef short int si;
typedef array <int, 6> a6;

//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int L[N], R[N];

void tranc(vector <char> &gr, int x)
{
    gr.clear();

    while (x > 0)
    {
        if (x % 2) gr.pb('1');
          else gr.pb('0');

        x /= 2;
    }

    reverse(gr.begin(), gr.end());
}

vector <char> dfs(int v)
{
    vector <char> l, r;

    if (L[v] < 0) l = dfs(abs(L[v])); else tranc(l, L[v]);

    if (R[v] < 0) r = dfs(abs(R[v])); else tranc(r, R[v]);

    if (sz(l) < sz(r)) swap(l, r);

    if (sz(l) != sz(r)) {l.pb('0'); return l;}

    for (int i = 0; i < sz(l); i++)
    {
        if (l[i] == r[i]) continue;

        if (r[i] == '1') swap(l, r);

        break;
    }

    l.pb('0');

    return l;
}

int main()
{
    //freopen("input.txt", "r", stdin); freopen("output4.txt", "w", stdout);

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

    int n;

    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        int l, r;

        cin >> l >> r;

        if (l < 0) L[i] = abs(l); else L[i] = -l;

        if (r < 0) R[i] = abs(r); else R[i] = -r;
    }

    vector <char> gr = dfs(1);

    for (auto it : gr) cout << it;
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 8 ms 1280 KB Output is correct
12 Correct 10 ms 1152 KB Output is correct
13 Correct 39 ms 5496 KB Output is correct
14 Correct 79 ms 11132 KB Output is correct
15 Correct 75 ms 1272 KB Output is correct
16 Correct 264 ms 27128 KB Output is correct
17 Correct 626 ms 56312 KB Output is correct
18 Correct 630 ms 64632 KB Output is correct
19 Correct 745 ms 42744 KB Output is correct
20 Correct 810 ms 182640 KB Output is correct