oj.uz

Submission #371079

# Submission time Handle Problem Language Result Execution time Memory
371079 2021-02-25T18:13:37 Z Atill83 Poklon (COCI17_poklon7) C++14
90 / 120
 873 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){
    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] = 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{
        if(idx[left].size() != idx[right].size()){
            return (idx[left].size() > idx[right].size() ? left : right);
        }

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

Subtask #1
90.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 109932 KB Output is correct
2 Correct 73 ms 109932 KB Output is correct
3 Correct 73 ms 109932 KB Output is correct
4 Correct 74 ms 110188 KB Output is correct
5 Correct 72 ms 109932 KB Output is correct
6 Correct 73 ms 110060 KB Output is correct
7 Correct 73 ms 109924 KB Output is correct
8 Correct 73 ms 110060 KB Output is correct
9 Incorrect 83 ms 110060 KB Output isn't correct
10 Correct 80 ms 110188 KB Output is correct
11 Correct 84 ms 112492 KB Output is correct
12 Correct 86 ms 112876 KB Output is correct
13 Correct 131 ms 122732 KB Output is correct
14 Correct 189 ms 135532 KB Output is correct
15 Correct 186 ms 130156 KB Output is correct
16 Correct 460 ms 191360 KB Output is correct
17 Runtime error 780 ms 262148 KB Execution killed with signal 9
18 Runtime error 762 ms 262148 KB Execution killed with signal 9
19 Runtime error 873 ms 262148 KB Execution killed with signal 9
20 Runtime error 494 ms 262148 KB Execution killed with signal 9