oj.uz

Submission #644023

# Submission time Handle Problem Language Result Execution time Memory
644023 2022-09-23T13:12:07 Z MinaRagy06 Poklon (COCI17_poklon7) C++17
108 / 120
 328 ms 90248 KB 
/**
 * file: practice.cpp
 * author: Mina Ragy
 * date: 23-09-2022
 */
#include <bits/stdc++.h>
using namespace std;
#define lesgooo ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl    '\n'
#define int     long long

const int N = 1e6+5;
int a[N][2], depth[N], dep, ans, add[N];
void rec(int i, int dpth)
{
    dep = max(dep, dpth+1);
    int lvl = dep-(dpth+1);
    lvl = (1ll<<min(lvl, 62ll));
    if (a[i][0] > 0) rec(a[i][0], dpth+1);
    else if (a[i][0] != 0 && lvl > 0) ans = max(ans, (abs(a[i][0])+lvl-1)/lvl);
    if (a[i][1] > 0) rec(a[i][1], dpth+1);
    else if (a[i][1] != 0 && lvl > 0) ans = max(ans, (abs(a[i][1])+lvl-1)/lvl);
}
void assign(int i, int dpth)
{
    int lvl = dep-(dpth+1);
    if (a[i][0] > 0) assign(a[i][0], dpth+1);
    if (a[i][0] < 0) for (int bit = 0; bit < 63; bit++) if ((ans>>bit)&1) add[bit+lvl]++;
    if (a[i][1] > 0) assign(a[i][1], dpth+1);
    if (a[i][1] < 0) for (int bit = 0; bit < 63; bit++) if ((ans>>bit)&1) add[bit+lvl]++;
}
signed main()
{
    lesgooo;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i][0] >> a[i][1], a[i][0] > 0? a[i][0]-- : 0, a[i][1] > 0? a[i][1]-- : 0;
    rec(0, 1), ans = 0, rec(0, 1),assign(0, 1);
    // cout << ans << endl;
    for (int i = 0; i < N-1; i++) add[i+1]+=add[i]/2, add[i]&=1;
    string s;
    for (int i = 0; i < N; i++) s.push_back(add[i]+'0');
    while (!(s.back()-'0')) s.pop_back();
    reverse(s.begin(), s.end()), cout << s;
    return 0;
}

Subtask #1
108.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 10128 KB Output is correct
2 Correct 17 ms 10224 KB Output is correct
3 Correct 17 ms 10128 KB Output is correct
4 Correct 17 ms 10128 KB Output is correct
5 Incorrect 17 ms 10128 KB Output isn't correct
6 Correct 17 ms 10188 KB Output is correct
7 Correct 17 ms 10124 KB Output is correct
8 Correct 17 ms 10128 KB Output is correct
9 Correct 17 ms 10256 KB Output is correct
10 Correct 17 ms 10264 KB Output is correct
11 Correct 20 ms 10632 KB Output is correct
12 Correct 21 ms 10752 KB Output is correct
13 Correct 33 ms 12916 KB Output is correct
14 Correct 49 ms 15812 KB Output is correct
15 Correct 50 ms 13320 KB Output is correct
16 Correct 126 ms 27260 KB Output is correct
17 Correct 257 ms 48344 KB Output is correct
18 Correct 259 ms 50644 KB Output is correct
19 Correct 328 ms 51464 KB Output is correct
20 Incorrect 315 ms 90248 KB Output isn't correct