제출 #1144581

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144581		not_amir	popa (BOI18_popa)	C++20	0 / 100	4 ms	416 KiB

popa

#include <bits/stdc++.h>
#include "popa.h"
using namespace std;

vector<int> parent;
vector<bool> seen;
int cntr;
void calc(int v, int p, int N) {
    while (v != p) {
        cntr = max(cntr, v);
        if (p != -1 && query(p, v, p, p)) {
            parent[v] = p;
            if (v < N && !query(v, v + 1, v + 1, v + 1))
                calc(v + 1, v, N);
        }
        else {
            if (query(v, v + 1, v + 1, v + 1))
                parent[v] = v + 1;
            else {
                calc(v + 1, v, N);
                if (cntr + 1 == N)
                    parent[v] = -1;
                else
                    parent[v] = cntr + 1;
            }
        }
        v = parent[v];
    }
}

int solve(int N, int* L, int* R) {
    cntr = 0;
    parent.assign(N, -1);
    seen.assign(N, false);
    seen[0] = seen[1] = true;
    calc(0, -1, N);
    for (int i = 0; i < N; i++)
        L[i] = R[i] = -1;
    int r = -1;
    for (int i = 0; i < N; i++) {
        if (parent[i] == -1)
            r = i;
        else {
            if (i < parent[i])
                L[parent[i]] = i;
            else
                R[parent[i]] = i;
        }
    }
    return r;
}

• Subtask 1: 0 / 37
• Subtask 2: 0 / 24
• Subtask 3: 0 / 39