oj.uz

Submission #371071

# Submission time Handle Problem Language Result Execution time Memory
371071 2021-02-25T17:44:42 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()); 
        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:52:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         if(l == idx[left].size() || idx[left][l] == '1')
      |            ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
48.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 55148 KB Output is correct
2 Correct 40 ms 55148 KB Output is correct
3 Correct 36 ms 55148 KB Output is correct
4 Incorrect 35 ms 55148 KB Output isn't correct
5 Incorrect 35 ms 55148 KB Output isn't correct
6 Correct 35 ms 55148 KB Output is correct
7 Incorrect 35 ms 55148 KB Output isn't correct
8 Incorrect 35 ms 55148 KB Output isn't correct
9 Incorrect 36 ms 55276 KB Output isn't correct
10 Correct 37 ms 55424 KB Output is correct
11 Correct 49 ms 57708 KB Output is correct
12 Correct 50 ms 58092 KB Output is correct
13 Correct 103 ms 68460 KB Output is correct
14 Incorrect 154 ms 81640 KB Output isn't correct
15 Incorrect 158 ms 76780 KB Output isn't correct
16 Incorrect 489 ms 140648 KB Output isn't correct
17 Execution timed out 1053 ms 251836 KB Time limit exceeded
18 Execution timed out 1061 ms 257932 KB Time limit exceeded
19 Execution timed out 1050 ms 262148 KB Time limit exceeded
20 Runtime error 724 ms 262148 KB Execution killed with signal 9