oj.uz

Submission #371068

# Submission time Handle Problem Language Result Execution time Memory
371068 2021-02-25T17:42:26 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){
    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:50:14: 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(l == idx[left].size() || idx[left][l] == '1')
      |            ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
48.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 55148 KB Output is correct
2 Correct 37 ms 55148 KB Output is correct
3 Correct 37 ms 55148 KB Output is correct
4 Incorrect 37 ms 55148 KB Output isn't correct
5 Incorrect 37 ms 55148 KB Output isn't correct
6 Incorrect 37 ms 55148 KB Output isn't correct
7 Correct 38 ms 55148 KB Output is correct
8 Incorrect 38 ms 55168 KB Output isn't correct
9 Incorrect 38 ms 55276 KB Output isn't correct
10 Incorrect 39 ms 55404 KB Output isn't correct
11 Correct 53 ms 57964 KB Output is correct
12 Correct 52 ms 58348 KB Output is correct
13 Correct 98 ms 69228 KB Output is correct
14 Correct 156 ms 83304 KB Output is correct
15 Incorrect 161 ms 78444 KB Output isn't correct
16 Incorrect 454 ms 143460 KB Output isn't correct
17 Execution timed out 1073 ms 253408 KB Time limit exceeded
18 Execution timed out 1028 ms 259404 KB Time limit exceeded
19 Execution timed out 1014 ms 262148 KB Time limit exceeded
20 Runtime error 686 ms 262148 KB Execution killed with signal 9