oj.uz

Submission #702825

# Submission time Handle Problem Language Result Execution time Memory
702825 2023-02-25T08:28:54 Z ecxx popa (BOI18_popa) C++17
37 / 100
 749 ms 436 KB 
#include <bits/stdc++.h>
#include "popa.h"

using namespace std;

int solve(int n,int* lc,int* rc) {

    vector<int> lp(1001, -1), rp(1001, -1), lupa(1001, -1), rupa(1001, -1), lch(1001, -1), rch(1001, -1);

    for (int i = 0; i < n; i++) {

        // find lp and rp !!

        int lo, hi, mid;

        lo=0;hi=i;

        while (lo < hi) {
            // accept 1s, reject 0s
            mid = (lo+hi)>>1;

            if (query(mid, i, i, i)) {
                hi = mid;
            } else { // =0
                lo = mid+1;
            }

        }

        lp[i] = lo-1;

        lo=i;hi=n-1;

        while (lo < hi) {
            // accept 1s, reject 0s
            mid = (lo+hi+1)>>1;

            if (query(i, mid, i, i)) {
                lo = mid;
            } else { // =0
                hi = mid-1;
            }

        }

        rp[i] = lo+1;
        
    }

    int ROOT;
    int pa;

    for (int i = 0; i < n; i++) if (lp[i]==-1 && rp[i]==n) {ROOT=i;}

    for (int i = 0; i < n; i++) {
        if (lp[i]==-1 && rp[i]==n && i != ROOT) {
            rupa[i] = ROOT;
            continue;
        }
        if (lp[i]==-1) {
            rupa[i] = rp[i];
            continue;
        }
        if (rp[i]==-1) {
            lupa[i] = lp[i];
            continue;
        }

        // compare the two, i guess

        if (rp[lp[i]] == rp[i]) { // go to the left lol
            lupa[i] = lp[i];
        } else {
            rupa[i] = rp[i];           
        }

    }

    for (int i = 0 ; i < n; i++) { // process left-parent in this order
        if (lupa[i]+1) {
            pa = lupa[i];
            while (rch[pa]+1) pa = rch[pa];
            rch[pa] = i;
        }
    }
    for (int i = n-1 ; i >= 0; i--) { // process right-parent in this order
        if (rupa[i]+1) {
            pa = rupa[i];
            while (lch[pa]+1) pa = lch[pa];
            lch[pa] = i;
        }
    }

    for (int i = 0; i < n; i++) {lc[i] = lch[i]; rc[i] = rch[i];}
    
    return ROOT;

}

Compilation message

popa.cpp: In function 'int solve(int, int*, int*)':
popa.cpp:96:12: warning: 'ROOT' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |     return ROOT;
      |            ^~~~

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 208 KB Output is correct
2 Correct 20 ms 208 KB Output is correct
3 Correct 40 ms 256 KB Output is correct
4 Correct 49 ms 208 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 749 ms 324 KB Output is correct
2 Correct 719 ms 436 KB Output is correct
3 Correct 437 ms 308 KB Output is correct
4 Runtime error 179 ms 312 KB Execution killed with signal 13
5 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 208 KB too many queries
2 Halted 0 ms 0 KB -