oj.uz

Submission #702810

# Submission time Handle Problem Language Result Execution time Memory
702810 2023-02-25T08:04:37 Z ecxx popa (BOI18_popa) C++17
37 / 100
 654 ms 416 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);

    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;
        
    }

    vector<int> lch(1001, -1);
    vector<int> rch(1001, -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) {
            if (lch[ROOT] + 1) {
                lch[i] = lch[ROOT];
            }
            lch[ROOT] = i; continue;
        }
        if (lp[i]==-1) {
            pa = rp[i];
            while (lch[pa] + 1) pa = lch[pa];
            lch[pa] = i;
            continue;
        }
        if (rp[i]==-1) {
            pa = lp[i];
            while (rch[pa] + 1) pa = rch[pa];
            rch[pa] = i;
            continue;
        }

        // compare the two, i guess

        if (rp[lp[i]] == rp[i]) { // go to the left lol
            pa = lp[i];
            while (rch[pa] + 1) pa = rch[pa];
            rch[pa] = i;
        } else {
            pa = rp[i];
            while (lch[pa] + 1) pa = lch[pa];
            lch[pa] = i;            
        }

    }

    for (int i = 0 ; i < n; i++) lc[i] = lch[i];
    for (int i = 0 ; i < n; 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 304 KB Output is correct
2 Correct 38 ms 208 KB Output is correct
3 Correct 31 ms 208 KB Output is correct
4 Correct 46 ms 308 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 648 ms 416 KB Output is correct
2 Correct 654 ms 316 KB Output is correct
3 Correct 373 ms 304 KB Output is correct
4 Runtime error 124 ms 304 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 -