code guessing, round #47 (completed)

/*
    Efficient longest increasing subsequence finding.
    Written for Code Guessing Round 47 (https://cg.esolangs.gay/47/).
    Input: Sequence of integers delimited by spacing, ex.: 4 5 2 6 3 5
    Output: Subsequence in the same format, ex.: 4 5 6

    Code may contain minor inconsistencies;
    the author was initially trying to conceal their style (this was for code guessing, after all)
    but then effectively backpedaled on that too.

    The author recommends using at least a gigabyte of IDE bloat to have a half-decent Groovy experience.
 */

class BigIntTree implements Iterable<Iterable<Integer>> {
    class Node {
        List<Integer> is
        Node left, right
    }
    Node root

    void set(BigInteger k, int i) {
        Node node = root ?= new Node()
        for (int j = k.bitLength() - 1; j > -1; --j)
            node = k.testBit(j) ? (node.right ?= new Node()) : (node.left ?= new Node())
        (node.is ?= []).add(i)
    }
    // Breadth-first traversal of the tree gives lets us traverse the keys in sorted order
    // in linear time in the total number of digits in the input
    @Override
    Iterator<Iterable<Integer>> iterator() {
        List<Node> lvl = root == null ? [] : [root]
        int i = 0
        return new Iterator<Iterable<Integer>>() {
            @Override
            boolean hasNext() {
                return !lvl.isEmpty()
            }

            @Override
            Iterable<Integer> next() {
                List<Integer> vs
                do {
                    vs = lvl.get(i).is
                    if (++i >= lvl.size()) {
                        List<Node> nlvl = []
                        for (nd in lvl) {
                            if (nd.left != null) nlvl.add(nd.left)
                            if (nd.right != null) nlvl.add(nd.right)
                        }
                        lvl = nlvl
                        i = 0
                    }
                } while (vs == null)
                return vs
            }
        }
    }
}

class Subseq {
    class Node {
        int i
        Node prev

        Node(int i, Node prev) {
            this.i = i
            this.prev = prev
        }
    }
    int len
    Node root
    static Subseq EMPTY = new Subseq()

    Subseq() {}

    Subseq(Subseq p, int i) {
        len = (p == null ? 0 : p.len) + 1
        root = new Node(i, p.root)
    }

    BigInteger[] apply(BigInteger[] seq) {
        def res = new BigInteger[len]
        def node = this.root
        for (def i = len - 1; i > -1; i--) {
            res[i] = seq[node.i]
            node = node.prev
        }
        return res
    }
}

class SegmentTree {
    class Node {
        Subseq subseq = Subseq.EMPTY
        Node left, right

        Node(int n) {
            assert (n > 0)
            if (n == 1) return
            def mid = n >> 1
            left = new Node(mid)
            right = new Node(n - mid)
        }
        // Get best subseq s with max(s) <= n
        Subseq get(int w, int n) {
            assert n <= w
            if (w == n)
                return subseq
            def mid = w >> 1
            if (n <= mid)
                return left.get(mid, n)
            def ssl = left.subseq
            def ssr = right.get(w - mid, n - mid)
            return (ssr.len > ssl.len) ? ssr : ssl
        }
        // Set new best subseq s for max(s) <= n
        void set(int w, int n, Subseq ss) {
            assert n <= w
            if (w == n) {
                if (ss.len > subseq.len)
                    subseq = ss
                return
            }
            if (ss.len > subseq.len)
                subseq = ss
            def mid = w >> 1
            if (n <= mid) {
                left.set(mid, n, ss)
                return
            }
            // Note: We can't install this for left, since left has a stricter bound
            right.set(w - mid, n - mid, ss)
        }
    }
    Node root
    int n

    SegmentTree(int n) {
        root = new Node(this.n = n)
    }

    Subseq get(int n) {
        return root.get(this.n, n)
    }

    Subseq set(int n, Subseq ss) {
        return root.set(this.n, n, ss)
    }
}

static BigInteger[] solve(BigInteger[] seq) {
    if (seq.length == 0) return new BigInteger[0]
    def t = new BigIntTree()
    for (int i = 0; i < seq.length; ++i)
        t.set(seq[i], i)
    // Remove gaps in the ordering.
    // This is important for achieving good time complexity.
    int o = 0
    def ordinals = new int[seq.length]
    for (is in t) {
        ++o
        for (i in is)
            ordinals[i] = o
    }
    // Do the "greedy" / "dynamic programming" solving
    // using a segment tree of best subsequences for upper bounds of the last element.
    def st = new SegmentTree(o)
    for (int i = 0; i < ordinals.length; ++i) {
        def n = ordinals[i]
        def ss = n == 1 ? Subseq.EMPTY : st.get(n - 1)
        st.set(n, new Subseq(ss, i))
    }
    return st.get(o).apply(seq)
}

static BigInteger[] read() {
    def sc = new Scanner(System.in)
    List<BigInteger> s = []
    while (sc.hasNext())
        s << new BigInteger(sc.next())
    return s.toArray(new BigInteger[s.size()])
}

static void write(BigInteger[] subseq) {
    print(subseq[0])
    for (int i = 1; i < subseq.length; i++) {
        print(" ")
        print(subseq[i])
    }
    println()
}

static void main(String[] args) {
    write(solve(read()))
}

/*
    Runtime analysis:

    Let the input be a sequence of n numbers encoded in some base
    (say, binary, or decimal, with at least one digit per number), delimited by some delimiter.
    Then the length of the input is O(m), where m is the total count of digits in the input (in any fixed base).
    Constructing the prefix tree to sort the numbers is O(m) then,
    as is traversing the prefix tree in level-order (breadth-first, left to right);
    replacing numbers with their ordinals is O(m) as well
    (incrementing the ordinal o would be amortized constant time even if o were a bigint).

    For each distinct ordinal, there needs to be a distinct number in the input.
    To encode k distinct numbers, you need Θ(log(k)) bits (on average) for each number.
    This implies an input length of Θ(n log(k)) (in bits, bytes, characters, whatever, as long as it's fixed size).
    (This also imposes an upper bound of O(log n) on the length of each ordinal in bits,
    which is why this implementation elects to represent ordinals as "just integers":
    larger sequences couldn't be represented using Java data structures anyways.)

    The next step maintains a "segment tree" which maps maxima to longest subsequences
    using only elements encountered so far (a prefix of the sequence).
    Since the largest value is the largest ordinal, this segment tree has depth log(k).
    For each element in the sequence, one get and set operation are issued.
    Since these operations can both easily be seen (*) to be O(log(k)),
    we obtain O(n log(k)), which is true linear time in the input size (in bits, not in integer registers).

    (*) For a simplified analysis, assume a perfect binary segment tree (that is, k is a power of two).
    We presume big integers (which this implementation does not use for aforementioned reasons,
    but which are nevertheless relevant for runtime analysis).
    Then the comparison `w == n` would not be constant time,
    but for each bit it has to compare, it saves having to dive a layer deeper, so it is fine.
    Since we split perfectly in the middle, `n <= mid` would only have to look at the most significant bit.
    `w - mid` / `n - mid` effectively just removes that most significant bit, thus is also constant time.

    A proof of correctness will be supplied when the author finds the time and motivation.
    For now, you will have to take the author's "trust me bro" for it.

    Exercises left to the reader:

    * Test this thoroughly to convince yourself of the correctness.
    * Constant-factor optimization of the binary tree / prefix tree:
      "Compress" long paths of multiple bits (trie -> patricia tree)
    * Constant-factor optimization of the segment tree:
      Store it in an array, avoids many heap allocations, improves cache locality.
    * Rewrite this in a "better" programming language.
 */

console.log("guess the api lmfao")

a = prompt().split(" ");
b = [];
c = 0;

while (c < a.length) {
	if (a[c] != "") {
		b.push(a[c]);
	};
	c++;
};

d = 0;
e = [];

while (d < b.length) {
	f=Number(b[d]);
	if (/^[0-9]*$/.test(f)) {
		e.push(f);
	};
	d++;
};

var f = function(g) {
	if (g.length == 0) {
		return [[]];
	} else if (g.length == 1) {
		return [g];
	} else {
		h = f(g.slice(1));
		i = 0;
		j = [];
		while (i < h.length) {
			if (g[0] < h[i][0]) {
				j.push([g[0]].concat(h[i]));
			};
			i++;
		};
		j.push([g[0]]);
		return h.concat(j);
	};
};

k = f(e);
l = 0;
m = 0;

while (l < k.length){
	if (k[l].length > m) {
		m = k[l].length;
	}
	l++;
}

n = 0;
o = [];

while (n < k.length){
	if (k[n].length == m) {
		o.push(k[n]);
	}
	n++;
};

p = 0;
while (p < o.length) {
	q = 0;
	while (q < o[p].length){
		process.stdout.write(o[p][q].toString()+" ");
		q++;
	};
	p++;
	console.log("|");
};

DZ|SD|E|CDD
r3_iEi|fiChtrf(fhi)t
l2_ZE|Z_Z|SxSylxy|_EE|E_Z|C_xC_ylxy
m2yx[1Zy|Ex](lxy)
^1xrCE(rmE(r[2naC(Cn(rmE(r[2Chta[1ZC(Cht)a|Ea](lhn)|aECEa]Ea)))a]Ex))

   #include <condition_variable>
 #include <scoped_allocator>
#include <initializer_list>
#include <source_location>
#include <memory_resource>
 #include <unordered_map>
   #include <unordered_set>
      #include <system_error>
         #include <shared_mutex>
            #include <forward_list>
                #include <string_view>
                     #include <type_traits>
                         #include <stacktrace>
                              #include <inttypes.h>
                                   #include <stop_token>
                                       #include <filesystem>
                                            #include <spanstream>
                                                #include <syncstream>
                                                   #include <functional>
                                                      #include <cinttypes>
                                                         #include <stdexcept>
                                                           #include <streambuf>
                                                            #include <execution>
                                                            #include <algorithm>
                                                            #include <semaphore>
                                                           #include <typeindex>
                                                         #include <exception>
                                                      #include <locale.h>
                                                   #include <limits.h>
                                                #include <iterator>
                                            #include <wctype.h>
                                       #include <stdfloat>
                                   #include <charconv>
                              #include <optional>
                         #include <signal.h>
                     #include <expected>
                #include <assert.h>
            #include <setjmp.h>
         #include <concepts>
      #include <stdint.h>
   #include <stddef.h>
 #include <typeinfo>
#include <stdarg.h>
#include <valarray>
#include <stdlib.h>
 #include <string.h>
   #include <iostream>
      #include <csetjmp>
         #include <cassert>
            #include <cwctype>
                #include <compare>
                     #include <variant>
                         #include <cstdlib>
                              #include <cstddef>
                                   #include <float.h>
                                       #include <ctype.h>
                                            #include <cstring>
                                                #include <cstdarg>
                                                   #include <csignal>
                                                      #include <errno.h>
                                                         #include <sstream>
                                                           #include <fstream>
                                                            #include <stdio.h>
                                                            #include <utility>
                                                            #include <numeric>
                                                           #include <climits>
                                                         #include <codecvt>
                                                      #include <version>
                                                   #include <cstdint>
                                                #include <barrier>
                                            #include <ostream>
                                       #include <wchar.h>
                                   #include <uchar.h>
                              #include <numbers>
                         #include <istream>
                     #include <iomanip>
                #include <complex>
            #include <clocale>
         #include <string>
      #include <cwchar>
   #include <vector>
 #include <limits>
#include <locale>
#include <cstdio>
#include <cctype>
 #include <cuchar>
   #include <ranges>
      #include <random>
         #include <iosfwd>
            #include <format>
                #include <atomic>
                     #include <bitset>
                         #include <cfloat>
                              #include <chrono>
                                   #include <future>
                                       #include <math.h>
                                            #include <thread>
                                                #include <time.h>
                                                   #include <cerrno>
                                                      #include <fenv.h>
                                                         #include <memory>
                                                           #include <mutex>
                                                            #include <cfenv>
                                                            #include <queue>
                                                            #include <ctime>
                                                           #include <stack>
                                                         #include <deque>
                                                      #include <latch>
                                                   #include <tuple>
                                                #include <cmath>
                                            #include <array>
                                       #include <regex>
                                   #include <ratio>
                              #include <list>
                         #include <span>
                     #include <bit>
                #include <ios>
            #include <new>
         #include <set>
      #include <any>
   #include <map>
 using namespace std;
// waiter waiter!
// more sexual transmited dieseses please!!
typedef struct
{ double val;
  int count;
  int prev;} Linky;
extern int entry(double *input, int len, double **output)
{ vector<Linky>things={};
  things.push_back(Linky{0,0,0});
  vector<int>thing_index={};
  unordered_map<double,int>maxlens={};
  vector<int*>imaxlens={};
  for(int i=0;i<len;i++)
  maxlens[input[i]]=1;
  for(int i=0;i<len;i++)
  imaxlens.push_back(&maxlens[input[i]]);
  int counter=0;
  int nextgc=1;
  vector<Linky>thingbuf={};
  for(int ii=0;ii<len;ii++)
  { auto x=input[ii];
    thingbuf.push_back(Linky{x,1,-1});
    counter++;
    Linky v;
    things[0].val=x;
    int mid=upper_bound(thing_index.begin(),thing_index.end(),0,
    [&](int a, int b){return things[a].val>things[b].val;})-thing_index.begin();
    for(int i=mid;i<thing_index.size()&&(v=things[thing_index[i]],1);i++)
    { if(v.count+1>*imaxlens[ii])
      { thingbuf.push_back(Linky{x,v.count+1,thing_index[i]});
        *imaxlens[ii]=v.count+1;
        counter++; }}
    auto oldend=thing_index.size();
    sort(thingbuf.begin(),thingbuf.end(),[&](auto a,auto b){return a.val>b.val;});
    for(auto v: thingbuf)
    thing_index.push_back(things.size()),things.push_back(v);
    inplace_merge(thing_index.begin(),thing_index.begin()+oldend,thing_index.end(),
    [&](int a, int b){return things[a].val>things[b].val;});
    if(counter>nextgc)
    { thing_index.resize(remove_if(thing_index.begin(),thing_index.end(),
      [&](auto i){return things[i].count<maxlens[things[i].val];})-thing_index.begin());
      nextgc+=thing_index.size(); }
    #ifdef ENTRY_DEBUG
    cout<<x<<" -> "<<mid<<" {"<<endl;int n=0;for(auto i:thing_index)
    {auto v=things[i];cout<<"  "<<(n++)<<": ";;for(;;v=things[v.prev])
    {cout<<v.val<<" ";if(v.prev==-1)break;}cout<<"\n";}
    cout<<"}\n";
    #endif
    thingbuf.clear(); }
  Linky bestest=things[1];
  int bestest_len=bestest.count;
  for(auto it=things.begin()+2;it<things.end();it++)
  { if(it->count>bestest_len)
    bestest=*it,
    bestest_len=it->count; }
  double* out;
  int count=0;
  Linky outlinky=bestest;
  for(;;outlinky=things[outlinky.prev])
  { count++;
    if(outlinky.prev==-1)break; }
  out=(double*)malloc(sizeof(double)*count);
  *output=out;
  outlinky=bestest;
  for(int i=0;;outlinky=things[outlinky.prev],i++)
  { if(i>=count) abort();
    out[i]=outlinky.val;
    if(outlinky.prev==-1)break; }
  reverse(out,out+count);
  return count; }
int main ()
{ vector<double>input=vector<double>();
  for(istream_iterator<double>it
     =istream_iterator<double>(cin);
  it!=istream_iterator<double>()
        ;it++)input.push_back(*it);
  double *out;
  int count=entry(input.data(),input.size(),&out);
  for(int i=0;i<count;i++)cout<<out[i]<<endl;
  free(out);
  return 0; }

findLongestIncreasingSubArray
	| longest current |
	longest := OrderedCollection new .
	current := OrderedCollection new .
	
	1 to: self size do: [ :i |
	self from: i to: self size do:
		[ :n |
			current isEmpty
				ifTrue:
					[ current add: n ]
				ifFalse:
					[ n > current last
						ifTrue: [ current add: n ] ] ] .
	longest size < current size
		ifTrue: [ longest := current ] .
	current := OrderedCollection new ] .
	^longest

{ 4. 5. 2. 6. 3. 5. } findLongestIncreasingSubarray .

let f1=function(F1:number[]):number[]{let f2:number[][]=[];
let F2: number[]=[];for(let f3:number=0;f3<F1.length;f3++){
;const                                                  F3:
number                                                    =
F1[f3];
let f4                                    :
number                                   []
=[];for(let f6=0;f6<f3;f6++){let F4=f2[f6];
var f5=F1[f6];if(f5<F3&&F4.length>f4.length
){;;f4=                                  F4
;}};;f2                                   [
+f3]=f4
.concat
();;;f2
[(f3)].
push((
F3));if
(f2[f3]
.length
>((F2))
.length
){F2=(f2)
[((f3))];}}
return (F2);};

use std::env;
use std::process::Command;

static mut ZERO: usize = 0;

fn diff<T: PartialEq + Clone>(x: &[T], y: &[T]) -> Vec<T> {
    let mut table: Vec<usize> = vec![0; x.len() * y.len()]; 
    let mut table_value = |i: usize, j: usize| unsafe {
        if i == usize::MAX || j == usize::MAX {
            &mut ZERO
        } else {
            &mut *(&mut table[j + i*y.len()] as *mut usize)
        }
    };

    for (j, b) in y.iter().enumerate() {
        for (i, a) in x.iter().enumerate() {
            *table_value(i, j) = if a == b {
                *table_value(i-1, j-1) + 1
            } else {
                *table_value(i-1, j).max(table_value(i, j-1))
            };
        }
    }

    let mut r = Vec::new();
    let mut i = x.len() - 1;
    let mut j = y.len() - 1;
    while i != usize::MAX && j != usize::MAX {
        if x[i] == y[j] {
            r.push(x[i].clone());
            i -= 1;
            j -= 1;
        } else if table_value(i, j-1) > table_value(i-1, j) {
            j -= 1;
        } else {
            i -= 1;
        }
    }

    r.reverse();
    r
}

pub fn lis(x: &[u32]) -> Vec<u32> {
    let mut v = x.to_owned();
    v.sort();
    v.dedup();
    diff(x, &v)
}

fn main() -> std::io::Result<()> {
    if cfg!(debug_assertions) {
        // shit.
        Command::new("rustc")
            .arg("-O")
            .arg(file!())
            .spawn()?
            .wait()?;
        Command::new("./ans")
            .args(env::args_os().skip(1))
            .spawn()?
            .wait()?;
        return Ok(());
    }

    let input: Vec<u32> = env::args().skip(1).map(|x| x.parse().unwrap()).collect();
    println!("{:?}", lis(&input));
    Ok(())
}

#include <iostream>
#include <vector>


template<typename T>
void print_vec_ (const char *vec_name,
                 std::vector<T> vec)
  {
    std::cout << vec_name << ":\n";
    for (const T &elem : vec)
      {
        std::cout << '\t';
        if (elem == UINTMAX_MAX)
          {
            std::cout << "-1";
          }
        else
          {
            std::cout << ' ' << elem;
          }
        std::cout << '\n';
      }
    std::cout << std::flush;
  }

#define print_vec(v) print_vec_(#v, v)



void print_loc_ (int src_line,
                 int cur_indx)
  {
    
    std::cout << '[' << src_line;
    if (cur_indx != -1)
      {
        std::cout << ':' << cur_indx;
      }
    std::cout << ']' << std::endl;
  }

#define print_loc(v) print_loc_(__LINE__, v)



template<typename T>
void print_val_ (const char* val_name,
                 T           val_vlue)
  {
    std::cout << val_name << ": ";
    std::cout << val_vlue << '\n';
    std::cout << std::flush;
  }

#define print_val(v) print_val_(#v, v)

#include <vector>
#include <cstdint>


namespace cg
  {
    using ui_m_t = std::uintmax_t;
    template<typename t>
    using vec = std::vector<t>;
    typedef vec<ui_m_t> vuimt;
    vuimt lung_incre_subsqn (const vec<std::uintmax_t> seq)
      {
        // stole an algorithm from wikipedia
        vuimt C;
        vuimt M;
        M.push_back(UINTMAX_MAX);
        ui_m_t Z = 0;
        for (ui_m_t Y = 0; Y < seq.size (); Y++)
          {
            ui_m_t l = 1, h = Z + 1, N;
            while (l < h)
              {
                ui_m_t m = l + ((h - l) / 2);
                if (seq.at(M.at(m)) >= seq.at(Y))
                  {
                    h = m;
                  } // if (seq.at(M.at(m)) >= seq.at(Y))
                else
                  {
                    l = m + 1;
                  } // else
              } // while (l < h)
            N = l;
            C.push_back(M.at(N - 1));
            if (N >= M.size())
              {
                M.push_back(Y);
              } // if (N >= M.size())
            else
              {
                M[N] = Y;
              } // else
            if (N > Z)
              {
                Z = N;
              } // if (N > Z)
          } // for (ui_m_t Y = 0; Y < seq.size (); Y++)
        std::vector<std::uintmax_t> H = vuimt( Z, 0 );
        ui_m_t f = M.at(Z);
        for (ui_m_t q = Z - 1; q < UINTMAX_MAX; q--)
          {
            H[q] = seq.at(f);
            f = C.at(f);
          } // for (ui_m_t q = Z - 1; q <= 0; q--)
        return H;
      } // vuimt lung_incre_subsqn (const vec<std::uintmax_t> seq)
  } // namespace cg