Submission #702810

#	Time	Username	Problem	Language	Result	Execution time	Memory
702810		ecxx	popa (BOI18_popa)	C++17	37 / 100	654 ms	416 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);

    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 (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