--- Final Solver (used for performance test) ---
import os
import subprocess
import ctypes
import sysconfig
import numpy as np
from typing import Any

CPP_CODE = r"""
#include <Python.h>
#include <vector>
#include <algorithm>

extern "C" void solve_fast(PyObject* list_obj, double* out_arr) {
    Py_ssize_t n = PyList_GET_SIZE(list_obj);
    std::vector<double> W(n);
    
    for (Py_ssize_t i = 0; i < n; i++) {
        PyObject* item = PyList_GET_ITEM(list_obj, i);
        double val = PyFloat_CheckExact(item) ? PyFloat_AS_DOUBLE(item) : PyFloat_AsDouble(item);
        out_arr[i] = val;
        W[i] = val;
    }
    
    double S = 0.0;
    int k = 0;
    
    double* w_ptr = W.data();
    int w_len = n;
    
    while (w_len > 0) {
        double p = w_ptr[w_len / 2];
        
        int lt = 0, eq = 0, gt = w_len - 1;
        double sum_G = 0.0;
        
        while (eq <= gt) {
            if (w_ptr[eq] > p) {
                sum_G += w_ptr[eq];
                std::swap(w_ptr[eq], w_ptr[lt]);
                lt++;
                eq++;
            } else if (w_ptr[eq] < p) {
                std::swap(w_ptr[eq], w_ptr[gt]);
                gt--;
            } else {
                eq++;
            }
        }
        
        int count_G = lt;
        int count_E = gt - lt + 1;
        
        double delta_S = sum_G + count_E * p;
        int delta_k = count_G + count_E;
        
        if ((S + delta_S) - (k + delta_k) * p > 1.0) {
            w_len = count_G;
        } else {
            S += delta_S;
            k += delta_k;
            w_ptr = w_ptr + gt + 1;
            w_len = w_len - (gt + 1);
        }
    }
    
    double theta = k > 0 ? (S - 1.0) / k : 0.0;
    
    for (Py_ssize_t i = 0; i < n; i++) {
        double val = out_arr[i] - theta;
        out_arr[i] = val > 0.0 ? val : 0.0;
    }
}
"""

class Solver:
    def __init__(self):
        self.so_path = "/tmp/libsolver_fast_final.so"
        if not os.path.exists(self.so_path):
            cpp_path = "/tmp/libsolver_fast_final.cpp"
            with open(cpp_path, "w") as f:
                f.write(CPP_CODE)
            
            include_dir = sysconfig.get_path("include")
            cmd = [
                "g++", "-O3", "-shared", "-fPIC", 
                f"-I{include_dir}", 
                cpp_path, "-o", self.so_path
            ]
            subprocess.run(cmd, check=True)
            
        self.lib = ctypes.CDLL(self.so_path)
        self.lib.solve_fast.argtypes = [ctypes.py_object, ctypes.c_void_p]
        self.lib.solve_fast.restype = None

    def solve(self, problem: dict, **kwargs) -> Any:
        y_list = problem.get("y")
        
        if not isinstance(y_list, list):
            if isinstance(y_list, np.ndarray):
                y_list = y_list.tolist()
            else:
                y_list = list(y_list)
                
        n = len(y_list)
        arr = np.empty(n, dtype=np.float64)
        
        self.lib.solve_fast(y_list, arr.ctypes.data_as(ctypes.c_void_p))
        
        return {"solution": arr}
--- End Solver ---
Running performance test...
============================= test session starts ==============================
platform linux -- Python 3.12.13, pytest-9.0.2, pluggy-1.6.0
rootdir: /tests
plugins: anyio-4.13.0, jaxtyping-0.3.9
collected 3 items

../tests/test_outputs.py .
--- Performance Summary ---
Validity: True
Total Baseline Time: 6.7843s
Total Solver Time:   0.8657s
Raw Speedup:         7.8370 x
Final Reward (Score): 7.8370
---------------------------
..

==================================== PASSES ====================================
=========================== short test summary info ============================
PASSED ../tests/test_outputs.py::test_solver_exists
PASSED ../tests/test_outputs.py::test_solver_validity
PASSED ../tests/test_outputs.py::test_solver_speedup
======================== 3 passed in 248.82s (0:04:08) =========================
