Submission #644023

#	Time	Username	Problem	Language	Result	Execution time	Memory
644023		MinaRagy06	Poklon (COCI17_poklon7)	C++17	108 / 120	328 ms	90248 KiB

poklon

/**
 * 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 / 120