Submission #702825

#	Time	Username	Problem	Language	Result	Execution time	Memory
702825		ecxx	popa (BOI18_popa)	C++17	37 / 100	749 ms	436 KiB

popa

#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 (stderr)

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 / 37
• Subtask 2: 0 / 24
• Subtask 3: 0 / 39