oj.uz

Submission #371075

# Submission time Handle Problem Language Result Execution time Memory
371075 2021-02-25T18:02:12 Z Atill83 Poklon (COCI17_poklon7) C++14
66 / 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(((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());
        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
66.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 55148 KB Output is correct
2 Correct 38 ms 55148 KB Output is correct
3 Correct 37 ms 55148 KB Output is correct
4 Correct 37 ms 55168 KB Output is correct
5 Correct 36 ms 55148 KB Output is correct
6 Incorrect 37 ms 55148 KB Output isn't correct
7 Correct 37 ms 55148 KB Output is correct
8 Incorrect 37 ms 55168 KB Output isn't correct
9 Incorrect 38 ms 55276 KB Output isn't correct
10 Correct 41 ms 55404 KB Output is correct
11 Correct 49 ms 57984 KB Output is correct
12 Correct 55 ms 58348 KB Output is correct
13 Correct 112 ms 68844 KB Output is correct
14 Correct 171 ms 82172 KB Output is correct
15 Incorrect 165 ms 77164 KB Output isn't correct
16 Incorrect 502 ms 141604 KB Output isn't correct
17 Execution timed out 1096 ms 252584 KB Time limit exceeded
18 Execution timed out 1083 ms 258768 KB Time limit exceeded
19 Execution timed out 1106 ms 254180 KB Time limit exceeded
20 Runtime error 730 ms 262148 KB Execution killed with signal 9