oj.uz

Submission #371081

# Submission time Handle Problem Language Result Execution time Memory
371081 2021-02-25T18:16:33 Z Atill83 Poklon (COCI17_poklon7) C++14
120 / 120
 754 ms 253156 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 5e6+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n;
int l[MAXN], r[MAXN];
int Gidx = 0;
string idx[MAXN];
int len[MAXN];
int say[MAXN];
int do_it(int v){
    if(v < 0){
        int cur = -v, pow = 1;
        while(cur){
            idx[Gidx] += (char)('0' + cur % 2);
            pow = pow * 2 % mod;
            cur /= 2;
        }
        reverse(idx[Gidx].begin(), idx[Gidx].end());
        say[Gidx] = -v;
        len[Gidx] = idx[Gidx].length();
        return Gidx++;
    }

    int left = do_it(l[v]), right = do_it(r[v]);
    int winner = -1;
    if(len[left] != len[right]){
        winner = (len[left] > len[right] ? left : right);
    }else{
        winner = (say[left] > say[right] ? left : right);
    }
    len[winner]++;
    return winner; 
}



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n;

    for(int i = 1; i <= n; i++)
        cin>>l[i]>>r[i];
    int ans = do_it(1);
    string & cev = idx[ans];

    while(cev.size() != len[ans])
        cev += '0';
    cerr<<ans<<endl;
    cout<<cev<<endl;



    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:63:22: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |     while(cev.size() != len[ans])
      |           ~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 156908 KB Output is correct
2 Correct 103 ms 156908 KB Output is correct
3 Correct 102 ms 156908 KB Output is correct
4 Correct 104 ms 156908 KB Output is correct
5 Correct 109 ms 156936 KB Output is correct
6 Correct 103 ms 156908 KB Output is correct
7 Correct 102 ms 156908 KB Output is correct
8 Correct 103 ms 156908 KB Output is correct
9 Correct 103 ms 156908 KB Output is correct
10 Correct 105 ms 157036 KB Output is correct
11 Correct 110 ms 157676 KB Output is correct
12 Correct 111 ms 157932 KB Output is correct
13 Correct 134 ms 160876 KB Output is correct
14 Correct 170 ms 164972 KB Output is correct
15 Correct 171 ms 163308 KB Output is correct
16 Correct 325 ms 182400 KB Output is correct
17 Correct 609 ms 215308 KB Output is correct
18 Correct 629 ms 217228 KB Output is correct
19 Correct 737 ms 225664 KB Output is correct
20 Correct 754 ms 253156 KB Output is correct