oj.uz

Submission #371078

# Submission time Handle Problem Language Result Execution time Memory
371078 2021-02-25T18:12:16 Z Atill83 Poklon (COCI17_poklon7) C++14
90 / 120
 861 ms 262148 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) 2e6+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];
vector<int> hsh[MAXN];
int do_it(int v){
    assert(Gidx <= MAXN);
    if(v < 0){
        int cur = -v, pow = 1;
        while(cur){
            idx[Gidx] += (char)('0' + cur % 2);
            hsh[Gidx].push_back(((hsh[Gidx].empty() ? 0 : hsh[Gidx].back()) + pow * (cur % 2) % mod) % mod);
            pow = pow * 2 % mod;
            cur /= 2;
        }
        reverse(idx[Gidx].begin(), idx[Gidx].end()); 
        reverse(hsh[Gidx].begin(), hsh[Gidx].end());
        len[Gidx] = hsh[Gidx].size();
        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{
        if(idx[left].size() != idx[right].size()){
            return (idx[left].size() > idx[right].size() ? left : right);
        }

        int yer = -1;
        for(yer = 0; yer < idx[left].size(); yer++){
            if(idx[left][yer] != idx[right][yer])
                break;
        }
        if(yer == idx[left].size() || idx[left][yer] == '1')
            winner = left;
        else
            winner = 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 do_it(int)':
poklon.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(yer = 0; yer < idx[left].size(); yer++){
      |                      ~~~~^~~~~~~~~~~~~~~~~~
poklon.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         if(yer == idx[left].size() || idx[left][yer] == '1')
      |            ~~~~^~~~~~~~~~~~~~~~~~~
poklon.cpp: In function 'int main()':
poklon.cpp:77:22: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |     while(cev.size() != len[ans])
      |           ~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
90.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 110060 KB Output is correct
2 Correct 72 ms 109932 KB Output is correct
3 Correct 82 ms 109932 KB Output is correct
4 Correct 74 ms 110012 KB Output is correct
5 Correct 73 ms 109976 KB Output is correct
6 Correct 73 ms 109932 KB Output is correct
7 Correct 73 ms 109932 KB Output is correct
8 Correct 73 ms 110080 KB Output is correct
9 Incorrect 74 ms 110060 KB Output isn't correct
10 Correct 75 ms 110316 KB Output is correct
11 Correct 91 ms 112492 KB Output is correct
12 Correct 86 ms 112748 KB Output is correct
13 Correct 130 ms 122732 KB Output is correct
14 Correct 192 ms 135660 KB Output is correct
15 Correct 187 ms 129900 KB Output is correct
16 Correct 467 ms 191360 KB Output is correct
17 Runtime error 778 ms 262144 KB Execution killed with signal 9
18 Runtime error 772 ms 262144 KB Execution killed with signal 9
19 Runtime error 861 ms 262148 KB Execution killed with signal 9
20 Runtime error 504 ms 262148 KB Execution killed with signal 9