oj.uz

Submission #371069

# Submission time Handle Problem Language Result Execution time Memory
371069 2021-02-25T17:43:01 Z Atill83 Poklon (COCI17_poklon7) C++14
48 / 120
 1000 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) 1e6+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];
vector<int> hsh[MAXN];
int do_it(int v){
    assert(Gidx <= MAXN);
    if(v < 0){
        int cur = -v;
        int pow = 1;
        while(cur){
            idx[Gidx] += (char)('0' + cur % 2);
            hsh[Gidx].push_back(pow * (cur % 2) % mod);
            pow = pow * 2 % mod;
            cur /= 2;
        }
        reverse(idx[Gidx].begin(), idx[Gidx].end()); 
        return Gidx++;
    }

    int left = do_it(l[v]), right = do_it(r[v]);
    int winner = -1;
    if(idx[left].size() != idx[right].size()){
        winner = (idx[left].size() > idx[right].size() ? left : right);
    }else{
        int l = 0, r = idx[left].size() - 1;
        
        while(l < r){
            int m = (l + r + 1) / 2;
            if(hsh[left][m] != hsh[right][m]){
                r = m - 1;
            }else{
                l = m;
            }
        }
        
        l++;
        if(l == idx[left].size() || idx[left][l] == '1')
            winner = left;
        else
            winner = right;
    }

    idx[winner] += '0';
    hsh[winner].push_back(hsh[winner].back() * 2 % mod);
    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];

    string & cev = idx[do_it(1)];

    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:51:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         if(l == idx[left].size() || idx[left][l] == '1')
      |            ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
48.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 55148 KB Output is correct
2 Correct 36 ms 55148 KB Output is correct
3 Correct 38 ms 55148 KB Output is correct
4 Incorrect 37 ms 55296 KB Output isn't correct
5 Incorrect 39 ms 55276 KB Output isn't correct
6 Incorrect 37 ms 55148 KB Output isn't correct
7 Correct 37 ms 55148 KB Output is correct
8 Incorrect 37 ms 55148 KB Output isn't correct
9 Incorrect 37 ms 55276 KB Output isn't correct
10 Incorrect 38 ms 55404 KB Output isn't correct
11 Correct 49 ms 57708 KB Output is correct
12 Correct 52 ms 58092 KB Output is correct
13 Correct 98 ms 68460 KB Output is correct
14 Correct 166 ms 81640 KB Output is correct
15 Incorrect 157 ms 76760 KB Output isn't correct
16 Incorrect 454 ms 140516 KB Output isn't correct
17 Execution timed out 1014 ms 251864 KB Time limit exceeded
18 Execution timed out 1033 ms 258012 KB Time limit exceeded
19 Execution timed out 1026 ms 262148 KB Time limit exceeded
20 Runtime error 682 ms 262148 KB Execution killed with signal 9