Skip to content

Instantly share code, notes, and snippets.

@ibmua

ibmua/Lossy2dCompression.cpp

Last active March 28, 2020 11:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ibmua/ae06986903be5a133bbfbb49befbb045 to your computer and use it in GitHub Desktop.
Save ibmua/ae06986903be5a133bbfbb49befbb045 to your computer and use it in GitHub Desktop.
Download ZIP
TopCoder Marathon Match 116 solution
Raw
Lossy2dCompression.cpp
/*
g++ -std=gnu++11 -fsanitize=address -O3 Lossy2dCompression.cpp -o Lossy2dCompression &&
java -jar tester.jar -exec "./Lossy2dCompression" -seed 9 -debug
g++ -std=gnu++11 -include bits/stdc++.h -O3 Lossy2dCompression.cpp -o Lossy2dCompression &&
java -jar tester.jar -exec "./Lossy2dCompression /path/to/store_result_for_seed_9 9" -seed 9 -novis
g++ -std=gnu++11 -include bits/stdc++.h -O3 Lossy2dCompression.cpp -o Lossy2dCompression &&
java -jar tester.jar -exec "./Lossy2dCompression /home/i/C/marathon/116/outs/a 9" -seed 9 -novis
g++ -std=gnu++11 bits/stdc++.h -O3
g++ -fsanitize=address -std=gnu++11 bits/stdc++.h -O3
time g++ Lossy2dCompression.cpp -D_FILE_OFFSET_BITS=64 -fsanitize=address -include bits/stdc++.h -O3 -std=c++17 -o Lossy2dCompression && ulimit -Sv 1000000000000 &&
./Lossy2dCompression < in-sample
*/
// C++11
#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wunused-result"
#pragma GCC diagnostic ignored "-Wregister"
// #pragma GCC optimize ("O3")
// #include "defines.cpp"
#include <sys/time.h>
#include <bits/stdc++.h> // precompiled header that includes EVERYTHING
// #include <iostream>
// #include <vector>
// #include <math.h> // remember M_PIl and M_PI !
// #include <queue> // queue, priority_queue
// #include <string>
// #include <deque>
// #include <algorithm>
// #include <set>
// #include <bitset>
// #include <unordered_set>
// #include <map>
// #include <unordered_map>
// #include <random>
// #include <utility>
// #include <numeric> // std::accumulate
// #include <tuple>
// #include <sstream>
// #include <stdlib.h> /* srand, rand */
// #include <fstream>
// #include <ctime> // std::time
// #include <time> // std::time
// #include <chrono>
// #include <exception>
// #include <boost/filesystem.hpp>
// #include <sys/stat.h>
// #include <parallel/algorithm>
// #include <thread>
// #include <mutex>
// #include <future>
// #include "matplotlibcpp.h"
// #include "stat-vals.h"
// #include "stat-keys.h"
// namespace plt = matplotlibcpp;
using namespace std;
int repeat_times = 1;
float randomization = 0.;
vector<string> stat_vals = {};
vector<string> stat_keys = {};
#define PRIME 919393
#define MIL 1000000
#define BILL (LL)1e9
#define BILLION (LL)1e9
#define QUAN (LL)1e18
#define QUANTILLION (LL)1e18
#define INT (__int128)
#define UINT (unsigned __int128)
#define LAZY_RND(to) ( mt_rnd()%to ) // 0 <= "LAZY" RND < to. May not be completely uniform
#define RND_ONE_IN(x) ( mt_rnd()%x == 0 )
#define RND_CHANCE_IS(x) ( zero_to_one_rnd(mt_rnd) < x )
#define RND_CHANCE ( zero_to_one_rnd(mt_rnd) ) // 0. <= RND_CHANCE <= 1.
#define RAND_CHANCE RND_CHANCE
#define SHUFFLE(r) shuffle( ALL(r) , mt_rnd);
#define ASSERT(exp, msg) assert(((void)msg, exp));
#define N_ARGS_SEQ(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,_11,N,...) N
#define N_ARGS(...) N_ARGS_SEQ(__VA_ARGS__, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
#define CONCAT(a, b) a ## b
#define CONCAT_2(a, b) CONCAT(a, b)
#define A first
#define B second
#define ALL(a) (a).begin(),(a).end()
#define PAIR make_pair
#define PAIR_XX_X(a,b,c) PAIR(PAIR(a,b),c)
#define PAIR_X_XX(a,b,c) PAIR(a,PAIR(b,c))
#define PAIR_XX_XX(a,b,c,d) PAIR(PAIR(a,b),PAIR(c,d))
#define SIZE(x) (int) x.size()
#define SZ(x) (int) x.size()
#define EMT(x) (0==x.size())
#define PSZ(x) (int) x->size()
#define FROM_PII(p, x,y) int x=p.A; int y=p.B;
#define SORT(x) sort( ALL(x) ); // 1 2 3 4
#define SORT_SMALL_FIRST(x) sort( ALL(x) ); // 1 2 3 4
#define SORT_c(x,c) sort( ALL(x), c ); // c(a,b) = a<b => 1 2 3 4 ... [true -> a first, false -> b first]
#define PQ priority_queue
#define UMAP unordered_map
#define USET unordered_set
#define VI vector<int>
#define VL vector<long>
#define LL long long
#define LD long double
#define VLL vector<long long>
#define V128 vector<INT>
#define VLD vector<long double>
#define VF vector<float>
#define VD vector<double>
#define VS vector< string >
#define VB vector< bool >
#define VVV(a) vector< vector< vector< a > > >
#define VVVV(a) vector< vector< vector< vector< a > > > >
#define VVVVV(a) vector< vector< vector< vector< vector< a > > > > >
#define VVL vector< vector<long> >
#define VVLL vector< vector<long long> >
#define VV128 vector< vector<INT> >
#define VVLD vector< vector<long double> >
#define VVI vector< vector<int> >
#define VVVI vector< VVI >
#define VVVVI vector< VVVI >
#define VVB vector< VB >
#define VVVB vector< VVB >
#define VVVVB vector< VVVB >
#define VVF vector< vector<float> >
#define VVD vector< vector<double> >
#define VVS vector< vector<string> >
#define P_FF pair<float, float>
#define VP_FF vector<P_FF>
#define VVP_FF vector<vector<P_FF>>
#define VVVP_FF vector<vector<vector<P_FF>>>
#define P_IF pair<int, float>
#define P_FI pair<float, int>
#define P_DI pair<double, int>
#define P_ID pair<int, double>
#define VP_IF vector< pair<int,float> >
#define VP_DI vector< pair<double,int> >
#define VP_ID vector< pair<int,double> >
#define VP_LDI vector< pair<LD,int> >
#define VP_ILD vector< pair<int,LD> >
#define VP_DD vector< pair<double, double> >
#define P_II pair<int, int>
#define P_II_I pair<P_II , int>
#define P_I_II pair<int , P_II>
#define VP_I_II vector< P_I_II >
#define VVP_I_II vector< VP_I_II >
#define P_F_II pair<float , P_II>
#define P_I_FI pair<int , P_FI>
#define P_I_DI pair<int , P_DI>
#define P_II_II pair<P_II, P_II>
#define P_DD pair<double, double>
#define VP_II vector< pair<int,int> >
#define VT_III vector< tuple<int,int,int> >
#define VP_FI vector< pair<float,int> >
#define VP_F_II vector< P_F_II >
#define VP_I_II vector< P_I_II >
#define VP_II_I vector< P_II_I >
#define VVP_FI vector< VP_FI >
#define VVP_II vector< VP_II >
#define VVVP_II vector< VVP_II >
#define VVVVP_II vector<VVVP_II >
#define P_LLLL pair<long long, long long>
#define VP_LLLL vector<pair<long long, long long>>
#define P_LL pair<long, long>
#define PUSH push_back
#define EMP emplace_back
#define C_SIZE(x) (sizeof(x) / sizeof(x[0]))
#define CLEAR(a) memset(a, 0, sizeof(a));
#define INF 2000000007
#define PUSH_XF_FX(x,y) push_back(PAIR(x,y))
#define PUSH_X_XX(x,y,z) push_back(PAIR( x , PAIR(y,z) ))
#define PUSH_XX_X(x,y,z) push_back(PAIR( PAIR(x,y) , z ))
#define UNIQ(v) unique( ALL(v) )
#define ONLY_UNIQUE(v) v.erase( UNIQ(v) , v.end() ); // Removes consecutive same
#define COPY_APPEND_TO(me,v) { me.resize(me.size() + v.size()); copy( ALL(v), me.end() - v.size()); }
#define APPEND_TO(me,v) me.insert( me.end() , ALL(v) );
#define APPEND_INTO_FROM_TO(me,v,f,t) me.insert( me.end() , v.begin() + min(SIZE(v),f), v.begin() + min(SIZE(v),t) );
#define ADD_BEFORE(me,v) me.insert( me.begin() , ALL(v) );
#define CLONE_A_TO_B(me,v) { v.resize( me.size() ); copy( ALL(me), v.begin() ); }
#define CLONE_VV_A_TO_B(a,b) { b.resize( a.size() ); F_all(i_224dk,b){ b[i_224dk].resize( a[i_224dk].size() ); copy( ALL(a[i_224dk]), b[i_224dk].begin() ); } }
#define REMOVE_TILL(me,i) { me.erase( me.begin() , me.begin() + i ); }
#define REMOVE_AFTER(me,i) { me.erase( me.begin() + i , me.end() ); }
#define REMOVE_RANGE(me,f,t) { me.erase( me.begin() + f , me.begin() + t ); }
#define REMOVE_I(from,i) { from.erase( from.begin() + i ); }
#define REMOVE_ITER(me,i) { me.erase( i ); }
#define REMOVE_VALUE(me,v) { REMOVE_ITER(me, FIND(me,v) ); }
#define REMOVE_FROM_SET(st,x) { st.erase( st.find(x) , st.end() ); }
#define REVERSE(myvector) reverse( ALL(myvector) );
#define V_MAX_I(v) distance(v.begin(), max_element( ALL(v) ))
#define V_MIN_I(v) distance(v.begin(), min_element( ALL(v) ))
#define V_0(v) v.resize(0);
#define RESIZE_DOWN_TO(v,to) v.resize( max(0, min(SZ(v), to)) );
#define MINIMIZE(a,b) a=min((a),(b));
#define MAXIMIZE(a,b) a=max((a),(b));
#define UNCONDITIONAL_UPDATE_4( best, nu, best_id, nu_id) { best = nu; best_id = nu_id; }
#define UNCONDITIONAL_UPDATE_6( best, nu, best_id, nu_id, best_2, nu_2) { best = nu; best_id = nu_id; best_2 = nu_2; }
#define UNCONDITIONAL_UPDATE_8( best, nu, best_id, nu_id, best_2, nu_2, best_3, nu_3) { best = nu; best_id = nu_id; best_2 = nu_2; best_3 = nu_3; }
#define IF_LESS_UPDATE_4( best, nu, best_id, nu_id) if(nu < best) { best = nu; best_id = nu_id; }
#define IF_MORE_UPDATE_4( best, nu, best_id, nu_id) if(nu > best) { best = nu; best_id = nu_id; }
#define IF_LESS_UPDATE_6( best, nu, best_id, nu_id, best_2, nu_2) if(nu < best) { best = nu; best_id = nu_id; best_2 = nu_2; }
#define IF_LESS_UPDATE_8( best, nu, best_id, nu_id, best_2, nu_2, best_3, nu_3) if(nu < best) { best = nu; best_id = nu_id; best_2 = nu_2; best_3 = nu_3; }
#define IF_MORE_UPDATE_6( best, nu, best_id, nu_id, best_2, nu_2) if(nu > best) { best = nu; best_id = nu_id; best_2 = nu_2; }
#define IF_MORE_UPDATE_8( best, nu, best_id, nu_id, best_2, nu_2, best_3, nu_3) if(nu > best) { best = nu; best_id = nu_id; best_2 = nu_2; best_3 = nu_3; }
#define IF_LESS_EQ_UPDATE_4( best, nu, best_id, nu_id) if( nu < best || (nu == best) ) { best = nu; best_id = nu_id; }
#define IF_MORE_EQ_UPDATE_4( best, nu, best_id, nu_id) if( nu > best || (nu == best) ) { best = nu; best_id = nu_id; }
#define IF_LESS_EQ_UPDATE_6( best, nu, best_id, nu_id, best_2, nu_2) if( nu < best || (nu == best) ) { best = nu; best_id = nu_id; best_2 = nu_2; }
#define IF_MORE_EQ_UPDATE_6( best, nu, best_id, nu_id, best_2, nu_2) if( nu > best || (nu == best) ) { best = nu; best_id = nu_id; best_2 = nu_2; }
#define IF_LESS_EQ_RND_UPDATE_4(best, nu, best_id, nu_id) if( nu < best || ((nu == best) && (rand()%2)) ) { best = nu; best_id = nu_id; }
#define IF_MORE_EQ_RND_UPDATE_4(best, nu, best_id, nu_id) if( nu > best || ((nu == best) && (rand()%2)) ) { best = nu; best_id = nu_id; }
#define IF_LESS_EQ_RND_UPDATE_6(best, nu, best_id, nu_id, best_2, nu_2) if( nu < best || ((nu == best) && (rand()%2)) ) { best = nu; best_id = nu_id; best_2 = nu_2; }
#define IF_MORE_EQ_RND_UPDATE_6(best, nu, best_id, nu_id, best_2, nu_2) if( nu > best || ((nu == best) && (rand()%2)) ) { best = nu; best_id = nu_id; best_2 = nu_2; }
#define IF_THEN_UPDATE_3 (cond, best_id, nu_id) if( cond ) { best_id = nu_id; }
#define IF_THEN_UPDATE_7(cond, best, nu, best_id, nu_id, best_2, nu_2) if( cond ) { best_id = nu_id; best_2 = nu_2; }
// #define IF_THEN_UPDATE_3(cond, best, nu, best_id, nu_id, best_2, nu_2) if( cond ) { best = nu; best_id = nu_id; best_2 = nu_2; }
#define UNCONDITIONAL_UPDATE(...) CONCAT_2(UNCONDITIONAL_UPDATE_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define IF_LESS_UPDATE(...) CONCAT_2(IF_LESS_UPDATE_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define IF_MORE_UPDATE(...) CONCAT_2(IF_MORE_UPDATE_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define IF_MORE_EQ_UPDATE(...) CONCAT_2(IF_MORE_EQ_UPDATE_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define IF_LESS_EQ_UPDATE(...) CONCAT_2(IF_LESS_EQ_UPDATE_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define IF_LESS_EQ_RND_UPDATE(...) CONCAT_2(IF_LESS_EQ_RND_UPDATE_,N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define IF_MORE_EQ_RND_UPDATE(...) CONCAT_2(IF_MORE_EQ_RND_UPDATE_,N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define IF_THEN_UPDATE(...) CONCAT_2(IF_THEN_UPDATE_,N_ARGS(__VA_ARGS__))(__VA_ARGS__)
// #define F(i,n) for (int i = 0; i < n; ++i)
#define F_step(i,t,st) for (int i = 0; i < t; i+=st )
#define F_from_step(i,f,t,st) for (int i = f; i < t; i+=st)
#define F_all(i,n) for (int i = 0; i < SIZE(n); ++i)
// #define F_all_elem(i,e,n) auto e=n[0]; for (int i = 0; i < SIZE(n); ++i, e=n[i])
// #define F_all_except_last(i,n) for (int i = 0; i < SIZE(n)-1; ++i)
// #define F_all_rev(i,n) for (int i = SIZE(n)-1; i >= 0; --i)
// #define F_rev(i,n) for (int i = n-1; i >= 0; --i)
// #define F_rev_till(i,till,n) for (int i = n-1; i >= till; --i)
#define F_from(i,f,t) for (auto i = f; i < t; ++i)
// #define F_from_till(i,f,t) for (auto i = f; i != t; f<t? i++ : i--)
#define F_elem(e,v) for (auto &e : v)
#define F_in(it,v) for (auto it = v.begin() ; it != v.end(); ++it)
#define F(n,i) for (int i = 0; i < (n); ++i) {
#define F_WHERE(n,i,c) for (int i = 0; i < n; ++i) if(c) {
// #define FTSI(f,t,s,i) for (int i = f; i != t; --i) {
#define F_REV(n,i) for (int i = n-1; i >= 0; --i) {
// #define F_F_T_DOWN(n,t,i) for (int i = (n); i >= (t); --i) {
#define F_FROM(n,i,f) for (int i = f; i < (n); ++i) {
#define F_I_F_T(i,f,t) for (int i = f; (f<t && i<=t) || (f>=t && i>=t); f<t ? ++i : --i) {
#define F_I_F_T_UP(i,f,t) for (int i = f; i<=t; ++i ) {
#define F_I_F_T_DOWN(i,f,t) for (int i = f; i>=t; --i ) {
#define F_I_F_T_S_UP(i,f,t,step) for (int i = f; i<=t; i+=step ) {
#define F_I_F_T_S_DOWN(i,f,t,step) for (int i = f; i>=t; i-=step ) {
#define F_I_F_T_W(i,f,t,w) for (int i = f; f<t ? i<=t : i>=t; f<t ? ++i : --i) if(w) {
#define F_I(v,i) for (int i = 0; i < SIZE(v); ++i) {
#define F_I_REV(v,i) for (int i = SIZE(v)-1; i >= 0; --i) {
#define F_I_FROM(v,i,f) for (int i = f; i < SIZE(v); ++i) {
#define F_I_E_F_T(v,i,e,f,t) for (int i = f; f<t ? i<=t : i>=t; f<t ? ++i : --i) { auto &e=v[i];
#define F_I_E_W(v,i,e,w) for (int i = 0; i < SIZE(v); ++i) if(w) { auto &e=v[i];
#define F_I_E(v,i,e) for (int i = 0; i < SIZE(v); ++i) { auto &e=v[i];
#define F_I_E_F(v,i,e,f) for (int i = f; i < SIZE(v); ++i) { auto &e=v[i];
#define F_I_E_F_T(v,i,e,f,t) for (int i = f; f<t ? i<=t : i>=t; f<t ? ++i : --i) { auto &e=v[i];
#define F_I_E_TO_MINUS(v,i,e,l) for (int i = 0; i < SIZE(v)-l; ++i) { auto &e=v[i];
#define F_I_E_TO(v,i,e,t) for (int i = 0; i < t; ++i) { auto &e=v[i];
#define F_I_E_REV(v,i,e) for (int i = SIZE(v)-1; i >= 0; --i) { auto &e=v[i];
#define F_I_E_REV_WHERE(v,i,e,w) for (int i = SIZE(v)-1; i >= 0; --i) if(w) { auto &e=v[i];
#define F_I_E_REV_FROM(v,i,e,s) for (int i = s; i >= 0; --i) { auto &e=v[i];
#define F_I_E_RANDOM(v,i,e,r) RANGE(r,0,SZ(v)-1); SHUFFLE(r); for (auto &i : r) { auto &e=v[i];
#define F_I_PE(v,i,ea,eb) for (int i = 0; i < SIZE(v); ++i) { auto &ea=v[i].A; auto &eb=v[i].B;
#define F_I_PE_FROM(v,i,ea,eb,f) for (int i = f; i < SIZE(v); ++i) { auto &ea=v[i].A; auto &eb=v[i].B;
#define F_VI(val,e) for (auto &e : VI val) {
#define F_E(v,e) for (auto &e : v) {
#define F_E_WHERE(v,e,w) for (auto &e : v) if(w) {
#define F_I_T_SHUFFLED_RANGE(i,t,r) RANGE(r,0,t); SHUFFLE(r) F_elem(i,r) //PARTIAL_RAND_RANGE(r,0,t,1) F_elem(i,r)
// #define F_where(i,n,c) for (int i = 0; i < n; ++i) if(c)
// #define F_step_where(i,t,st,c) for (int i = 0; i < t; i+=st ) if(c)
// #define F_from_step_where(i,f,t,st,c) for (int i = f; i < t; i+=st) if(c)
// #define F_all_where(i,n,c) for (int i = 0; i < SIZE(n); ++i) if(c)
// #define F_all_elem_where(i,e,n,c) auto e=n[i]; for (int i = 0; i < SIZE(n); ++i) if(c)
// #define F_all_except_last_where(i,n,c) for (int i = 0; i < SIZE(n)-1; ++i) if(c)
// #define F_all_rev_where(i,n,c) for (int i = SIZE(n)-1; i >= 0; --i) if(c)
// #define F_rev_where(i,n,c) for (int i = n-1; i >= 0; --i) if(c)
// #define F_rev_till_where(i,till,n,c) for (int i = n-1; i >= till; --i) if(c)
// #define F_from_where(i,f,t,c) for (auto i = f; i < t; ++i) if(c)
// #define F_from_till_where(i,f,t,c) for (auto i = f; i != t; f<t? i++ : i--) if(c)
// #define F_elem_where(e,v,c) for (auto &e : v) if(c)
// #define F_iter_where(it,v,c) for (auto it = v.begin() ; it != v.end(); ++it) if(c)
// #define F_iter_rev_where(it,v,c) for (auto it = v.rbegin() ; it != v.rend(); ++it) if(c)
// #define F_iter_rev(it,v) for (auto it = v.rbegin() ; it != v.rend(); ++it)
#define RANGE(rng,f,t) VI rng(t-f); F_from(i_3483,f,t){ rng[i_3483] = i_3483; }
// #define ZERO_PLUS(x) max(0, x)
#define BIN_SEARCH(v,val) binary_search( ALL(v), val )
#define BIN_SEARCH_c(v,val,c) binary_search( ALL(v), val, c )
#define UP_BOUND_I(V,val) upper_bound( ALL(V) ,val ) - V.begin()
#define LOW_BOUND_I(V,val) lower_bound( ALL(V) ,val ) - V.begin()
#define UP_BOUND_I_c(V,val,c) upper_bound( ALL(V) ,val, c ) - V.begin()
#define LOW_BOUND_I_c(V,val,c) lower_bound( ALL(V) ,val, c ) - V.begin()
#define FIND(me,val) find( ALL(me), val )
#define FIND_I(set_,val) FIND(set_,val) - set_.begin()
#define THIS_EL_INSIDE(k,set_) set_.find( k ) != set_.end()
#define THIS_EL_NOT_INSIDE(k,set_) set_.find( k ) == set_.end()
#define IF_THIS_EL_INSIDE(k,set_) if( set_.find( k ) != set_.end() )
#define IF_THIS_EL_NOT_INSIDE(k,set_) if( set_.find( k ) == set_.end() )
#define THIS_EL_INSIDE_V(e,v) find( ALL(v) , e ) != v.end()
#define THIS_EL_NOT_INSIDE_V(e,v) find( ALL(v) , e ) == v.end()
#define IF_THIS_EL_INSIDE_V(e,v) if( find( ALL(v) , e ) != v.end() )
#define IF_THIS_EL_NOT_INSIDE_V(e,v) if( find( ALL(v) , e ) == v.end() )
#define FILL(me,v) fill(me.begin(), me.end(), v);
#define ZERO(me) FILL(me, 0);
#define BAR_VI_FROM_MAP(vi,m) VI vi; F(i, (*m.rbegin()).A +1 ){vi.PUSH( m[i] ); } plt::figure_size(1920*2/3, 1080*2/3); plt::bar( vi );
#define BAR_FROM_MAP(m) VI vi; F(i, (*m.rbegin()).A +1 ){vi.PUSH( m[i] ); } plt::figure_size(1920*2/3, 1080*2/3); plt::bar( vi );
#define SAVE_BAR_FROM_MAP_AS(m,name) VI vi; F(i, (*m.rbegin()).A +1 ){vi.PUSH( m[i] ); } plt::figure_size(1920*2/3, 1080*2/3); plt::bar( vi ); plt::save( name );
#define BAR_FROM_VI(vi) plt::figure_size(1920*2/3, 1080*2/3); plt::bar( vi );
#define SAVE_BAR_FROM_VI_AS(vi,name) plt::figure_size(1920*2/3, 1080*2/3); plt::bar( vi ); plt::save( name );
#define CLOCK_TIME_S(f,t) (t - f) / (double)CLOCKS_PER_SEC
#define CLOCK_TIME_SINCE(f) (clock() - f) / (double)CLOCKS_PER_SEC
#define TIME(now) gettimeofday(&now, NULL);
#define TIME_NOW(now) struct timeval now; gettimeofday(&now, NULL);
#define STR(a) to_string(a)
#define CHAR_STR(a) string(1,a)
#define COL_BLK ((string)"\033[30m" )
#define COL_R ((string)"\033[31m" )
#define COL_R_BG ((string)"\033[41m" ) + COL_BLK
#define COL_G ((string)"\033[32m" )
#define COL_G_BG ((string)"\033[42m" ) + COL_BLK
#define COL_B ((string)"\033[34m" )
#define COL_B_BG ((string)"\033[44m" )
#define COL_Y ((string)"\033[93m" )
#define COL_Y_BG ((string)"\033[43m" ) + COL_BLK
#define COL_END ((string)"\033[0m" )
#define END std::endl
#define OUTnl {std::cout << COL_END << endl;} // new line
#define OUT_LINE {std::cout << endl;} // new line
#define OUT_1(x) {std::cout << COL_END+(string)" " << x << COL_END << endl;}
#define OUT_2(x,y) {std::cout << COL_END+(string)" " << x << COL_END+" " << y << COL_END<< endl;}
#define OUT_3(x,y,z) {std::cout << COL_END+(string)" " << x << COL_END+" " << y << COL_END+" " << z << COL_END << endl;}
#define OUT_4(x,y,z,k) {std::cout << COL_END+(string)" " << x << COL_END+" " << y << COL_END+" " << z << COL_END+" " << k << COL_END << endl;}
#define OUT_5(x,y,z,k,l) {std::cout << COL_END+(string)" " << x << COL_END+" " << y << COL_END+" " << z << COL_END+" " << k << COL_END+" " << l << COL_END << endl;}
#define OUT_6(x,y,z,k,l,u) {std::cout << COL_END+(string)" " << x << COL_END+" " << y << COL_END+" " << z << COL_END+" " << k << COL_END+" " << l << COL_END+" " << u << COL_END << endl;}
#define OUT_7(x,y,z,k,l,u,p) {std::cout << COL_END+(string)" " << x << COL_END+" " << y << COL_END+" " << z << COL_END+" " << k << COL_END+" " << l << COL_END+" " << u << COL_END+" " << p << COL_END << endl;}
#define OUT_8(x,y,z,k,l,u,p,h) {std::cout << COL_END+(string)" " << x << COL_END+" " << y << COL_END+" " << z << COL_END+" " << k << COL_END+" " << l << COL_END+" " << u << COL_END+" " << p << COL_END+" " << h << COL_END << endl;}
#define OUT_9(x,y,z,k,l,u,p,h,b) {std::cout << COL_END+(string)" " << x << COL_END+" " << y << COL_END+" " << z << COL_END+" " << k << COL_END+" " << l << COL_END+" " << u << COL_END+" " << p << COL_END+" " << h << COL_END+" " << b << COL_END << endl;}
#define OUT_10(x,y,z,k,l,u,p,h,b,m) {std::cout << COL_END+(string)" " << x << COL_END+" " << y << COL_END+" " << z << COL_END+" " << k << COL_END+" " << l << COL_END+" " << u << COL_END+" " << p << COL_END+" " << h << COL_END+" " << b << COL_END+" " << m << COL_END << endl;}
#define OUT_11(x,y,z,k,l,u,p,h,b,m,w) {std::cout << COL_END+(string)" " << x << COL_END+" " << y << COL_END+" " << z << COL_END+" " << k << COL_END+" " << l << COL_END+" " << u << COL_END+" " << p << COL_END+" " << h << COL_END+" " << b << COL_END+" " << m << COL_END+" " << w << COL_END << endl;}
#define COUT_1(x) {std::cout << x << endl;}
#define COUT_2(x,y) {std::cout << x << " " << y << endl;}
#define COUT_3(x,y,z) {std::cout << x << " " << y << " " << z << endl;}
#define COUT_4(x,y,z,k) {std::cout << x << " " << y << " " << z << " " << k << endl;}
#define COUT_5(x,y,z,k,l) {std::cout << x << " " << y << " " << z << " " << k << " " << l << endl;}
#define COUT_6(x,y,z,k,l,u) {std::cout << x << " " << y << " " << z << " " << k << " " << l << " " << u << endl;}
#define COUT_7(x,y,z,k,l,u,p) {std::cout << x << " " << y << " " << z << " " << k << " " << l << " " << u << " " << p << endl;}
#define COUT_8(x,y,z,k,l,u,p,h) {std::cout << x << " " << y << " " << z << " " << k << " " << l << " " << u << " " << p << " " << h << endl;}
#define COUT_9(x,y,z,k,l,u,p,h,b) {std::cout << x << " " << y << " " << z << " " << k << " " << l << " " << u << " " << p << " " << h << " " << b << endl;}
#define COUT_10(x,y,z,k,l,u,p,h,b,m) {std::cout << x << " " << y << " " << z << " " << k << " " << l << " " << u << " " << p << " " << h << " " << b << " " << m << endl;}
#define CERR_1(x) {std::cerr << COL_END+(string)" " << x << COL_END << endl;}
#define CERR_2(x,y) {std::cerr << COL_END+(string)" " << x << COL_END+" " << y << COL_END<< endl;}
#define CERR_3(x,y,z) {std::cerr << COL_END+(string)" " << x << COL_END+" " << y << COL_END+" " << z << COL_END << endl;}
#define CERR_4(x,y,z,k) {std::cerr << COL_END+(string)" " << x << COL_END+" " << y << COL_END+" " << z << COL_END+" " << k << COL_END << endl;}
#define CERR_5(x,y,z,k,l) {std::cerr << COL_END+(string)" " << x << COL_END+" " << y << COL_END+" " << z << COL_END+" " << k << COL_END+" " << l << COL_END << endl;}
#define CERR_6(x,y,z,k,l,u) {std::cerr << COL_END+(string)" " << x << COL_END+" " << y << COL_END+" " << z << COL_END+" " << k << COL_END+" " << l << COL_END+" " << u << COL_END << endl;}
#define CERR_7(x,y,z,k,l,u,p) {std::cerr << COL_END+(string)" " << x << COL_END+" " << y << COL_END+" " << z << COL_END+" " << k << COL_END+" " << l << COL_END+" " << u << COL_END+" " << p << COL_END << endl;}
#define CERR_8(x,y,z,k,l,u,p,h) {std::cerr << COL_END+(string)" " << x << COL_END+" " << y << COL_END+" " << z << COL_END+" " << k << COL_END+" " << l << COL_END+" " << u << COL_END+" " << p << COL_END+" " << h << COL_END << endl;}
#define CERR_9(x,y,z,k,l,u,p,h,b) {std::cerr << COL_END+(string)" " << x << COL_END+" " << y << COL_END+" " << z << COL_END+" " << k << COL_END+" " << l << COL_END+" " << u << COL_END+" " << p << COL_END+" " << h << COL_END+" " << b << COL_END << endl;}
#define CERR_10(x,y,z,k,l,u,p,h,b,m) {std::cerr << COL_END+(string)" " << x << COL_END+" " << y << COL_END+" " << z << COL_END+" " << k << COL_END+" " << l << COL_END+" " << u << COL_END+" " << p << COL_END+" " << h << COL_END+" " << b << COL_END+" " << m << COL_END << endl;}
#define CERR_11(x,y,z,k,l,u,p,h,b,m,w) {std::cerr << COL_END+(string)" " << x << COL_END+" " << y << COL_END+" " << z << COL_END+" " << k << COL_END+" " << l << COL_END+" " << u << COL_END+" " << p << COL_END+" " << h << COL_END+" " << b << COL_END+" " << m << COL_END+" " << w << COL_END << endl;}
#define OUT(...) CONCAT_2(OUT_ , N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define COUT(...) CONCAT_2(COUT_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define CERR(...) CONCAT_2(CERR_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define OUT_map(m) F_elem(e, m ){ OUT_2( e.A, e.B )}
#define OUT_MATRIX(m) { F_all(i_22d,m){cout<<i_22d<<" "; F_all(j_3da, m[i_22d] ){cout<<m[i_22d][j_3da]<<" ";} OUT_LINE } }
#define OUT_P(i) std::cout<<i.A<<" "<<i.B<<END;
#define CaseOUT(tt,...) COUT("Case #" + STR(tt) + ":" , __VA_ARGS__)
#define SET_COUT_PRECISION(v) cout.precision(v);
#define SET_COUT_FIX_PRECISION cout.setf( std::ios::fixed, std:: ios::floatfield );
#define SET_FAKE_INPUT_STORE_TRUE(s,t) t=cout.rdbuf(); istringstream fake_iss(s); cin.rdbuf( fake_iss.rdbuf());
#define SET_FAKE_INPUT(s) istringstream fake_iss(s); cin.rdbuf(fake_iss.rdbuf());
#define SET_TRUE_INPUT(input) cin.rdbuf(input);
#define CIN_S(i) string i; std::cin>>i;
#define CIN_P1(i) P_II i; std::cin>>i.A>>i.B;
#define CIN_P2(i) P_II i,j; std::cin>>i.A>>i.B>>j.A>>j.B;
#define CIN_LL1(i) long long i; std::cin>>i;
#define CIN_LL2(i,j) long long i,j; std::cin>>i>>j;
#define CIN_LL3(i,j,k) long long i,j,k; std::cin>>i>>j>>k;
#define CIN_LL4(i,j,k,x) long long i,j,k,x; std::cin>>i>>j>>k>>x;
#define CIN_I1(i) int i; std::cin>>i;
#define CIN_I2(i,j) int i,j; std::cin>>i>>j;
#define CIN_I3(i,j,k) int i,j,k; std::cin>>i>>j>>k;
#define CIN_I4(i,j,k,x) int i,j,k,x; std::cin>>i>>j>>k>>x;
#define CIN_F1(i) float i; std::cin>>i;
#define CIN_F2(i,j) float i,j; std::cin>>i>>j;
#define CIN_F3(i,j,k) float i,j,k; std::cin>>i>>j>>k;
#define CIN_F4(i,j,k,x) float i,j,k,x; std::cin>>i>>j>>k>>x;
#define CIN_D1(i) double i; std::cin>>i;
#define CIN_D2(i,j) double i,j; std::cin>>i>>j;
#define CIN_D3(i,j,k) double i,j,k; std::cin>>i>>j>>k;
#define CIN_D4(i,j,k,x) double i,j,k,x; std::cin>>i>>j>>k>>x;
#define CIN_1(i) cin>>i;
#define CIN_2(i,j) cin>>i>>j;
#define CIN_3(i,j,k) cin>>i>>j>>k;
#define CIN_4(i,j,k,x) cin>>i>>j>>k>>x;
#define CIN_5(i,j,k,x,o) cin>>i>>j>>k>>x>>o;
#define IN_LL_1(i) long long i; infile>>i;
#define IN_LL_2(i,j) long long i,j; infile>>i>>j;
#define IN_LL_3(i,j,k) long long i,j,k; infile>>i>>j>>k;
#define IN_LL_4(i,j,k,x) long long i,j,k,x; infile>>i>>j>>k>>x;
#define IN_S_1(i) string i; infile>>i;
#define IN_S_2(i) string i,j; infile>>i>>j;
#define IN_S_3(i) string i,j,k; infile>>i>>j>>k;
#define IN_S_4(i) string i,j,k,x; infile>>i>>j>>k>>x;
#define IN_P_1(i) P_II i; infile>>i.A>>i.B;
#define IN_P_2(i,j) P_II i,j; infile>>i.A>>i.B>>j.A>>j.B;
#define IN_I_1(i) int i; infile>>i;
#define IN_I_2(i,j) int i,j; infile>>i>>j;
#define IN_I_3(i,j,k) int i,j,k; infile>>i>>j>>k;
#define IN_I_4(i,j,k,x) int i,j,k,x; infile>>i>>j>>k>>x;
#define IN_D_1(i) double i; infile>>i;
#define IN_D_2(i,j) double i,j; infile>>i>>j;
#define IN_D_3(i,j,k) double i,j,k; infile>>i>>j>>k;
#define IN_D_4(i,j,k,x) double i,j,k,x; infile>>i>>j>>k>>x;
#define IN_F_1(i) float i; infile>>i;
#define IN_F_2(i,j) float i,j; infile>>i>>j;
#define IN_F_3(i,j,k) float i,j,k; infile>>i>>j>>k;
#define IN_F_4(i,j,k,x) float i,j,k,x; infile>>i>>j>>k>>x;
#define IN_1(i) infile>>i;
#define IN_2(i,j) infile>>i>>j;
#define IN_3(i,j,k) infile>>i>>j>>k;
#define IN_4(i,j,k,x) infile>>i>>j>>k>>x;
#define IN_5(i,j,k,x,o) infile>>i>>j>>k>>x>>o;
#define IN_I_PUSH(a) {IN_I(g2341) a.PUSH(g2341);}
#define IN_S_PUSH(a) {IN_S(g2341) a.PUSH(g2341);}
#define IN_F_PUSH(a) {IN_F(g2341) a.PUSH(g2341);}
#define IN_P_PUSH(a) {IN_P(g2341) a.PUSH(g2341);}
#define FOUT_P(i) outf<<i.A<<" "<<i.B<<END;
#define FOUT_1(i) outf<<i<<END;
#define FOUT_2(i,j) outf<<i<<" "<<j<<END;
#define FOUT_3(i,j,k) outf<<i<<" "<<j<<" "<<k<<END;
#define FOUT_4(i,j,k,x) outf<<i<<" "<<j<<" "<<k<<" "<<x<<END;
#define FOUT_5(i,j,k,x,y) outf<<i<<" "<<j<<" "<<k<<" "<<x<<" "<<y<<END;
#define FOUT_6(i,j,k,x,y,z) outf<<i<<" "<<j<<" "<<k<<" "<<x<<" "<<y<<" "<<z<<END;
#define FOUT_map(m) F_elem(e, m ){ FOUT_2( e.A, e.B )}
#define FOUT(...) CONCAT_2(FOUT_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define CIN_I(...) CONCAT_2(CIN_I, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define CIN_LL(...) CONCAT_2(CIN_LL, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define CIN_F(...) CONCAT_2(CIN_F, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define CIN_D(...) CONCAT_2(CIN_D, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define CIN(...) CONCAT_2(CIN_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define IN(...) CONCAT_2(IN_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define IN_I(...) CONCAT_2(IN_I_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define IN_LL(...) CONCAT_2(IN_LL_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define IN_D(...) CONCAT_2(IN_D_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define IN_F(...) CONCAT_2(IN_F_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define IN_P(...) CONCAT_2(IN_P_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define IN_S(...) CONCAT_2(IN_S_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
// ARRAYS NEED TO BE SORTED FIRST
#define UNION_A_B_TO(a,b,to) set_union (ALL(a),ALL(b),back_inserter(to));
#define INTERSECTION_A_B_TO(a,b,to) set_intersection(ALL(a),ALL(b),back_inserter(to));
#define SUM_VI(v) accumulate( v.begin(), v.end(), 0LL)
#define SUM_VF(v) accumulate( v.begin(), v.end(), 0.)
#define F_AVG_VI(v) (float) SUM_VI(v) / (float) v.size()
#define F_AVG_VF(v) SUM_VF(v) / (double) v.size()
#define MEDIAN(v,m) auto prtly_srtd = v; nth_element(prtly_srtd.begin(), prtly_srtd.begin() + prtly_srtd.size()/2, prtly_srtd.end()); auto m = v[v.size()/2];
#define ADD_TO_V(v,by) { F_all(i_9dx, v){ v[i_9dx]+=by; } }
#define SUBTRACT_FROM_V(v,by) { F_all(i_9dx, v){ v[i_9dx]-=by; } }
#define MULTIPLY_V_BY(v,by) { F_all(i_9dx, v){ v[i_9dx]*=by; } }
#define DIVIDE_V_BY(v,by) { long double by_rev = (long double)1./(long double)by; MULTIPLY_V_BY(v,by_rev) }
#define ADD_TO_VV(v,by) { F_all(j_4dx, v){ ADD_TO_V (v[j_4dx] , by); } }
#define SUBTRACT_FROM_VV(v,by) { F_all(j_4dx, v){ SUBTRACT_FROM_V (v[j_4dx] , by); } }
#define MULTIPLY_VV_BY(v,by) { F_all(j_4dx, v){ MULTIPLY_V_BY (v[j_4dx] , by); } }
#define DIVIDE_VV_BY(v,by) { long double by_rev_x = (long double)1./(long double)by; MULTIPLY_VV_BY(v,by_rev_x) }
#define ADD_V(v,b) { F(i_94kd, min( SIZE(v) , SIZE(b) ) ){ v[i_94kd]+=b[i_94kd]; } }
#define SUBTRACT_V(v,b) { F(i_94kd, min( SIZE(v) , SIZE(b) ) ){ v[i_94kd]-=b[i_94kd]; } }
#define MULTIPLY_V(v,b) { F(i_94kd, min( SIZE(v) , SIZE(b) ) ){ v[i_94kd]*=b[i_94kd]; } }
#define DIVIDE_BY_V(v,b) { F(i_94kd, min( SIZE(v) , SIZE(b) ) ){ v[i_94kd]/=b[i_94kd]; } }
#define DIVIDE_BY_V_LD(v,b) { F(i_94kd, min( SIZE(v) , SIZE(b) ) ){ v[i_94kd] =(long double)v[i_94kd] / (long double)b[i_94kd]; } }
#define ADD_VV(v,b) { F(i_4857, min( SIZE(v) , SIZE(b) ) ){ ADD_V (v[i_4857] , b[i_4857]) } }
#define SUBTRACT_VV(v,b) { F(i_4857, min( SIZE(v) , SIZE(b) ) ){ SUBTRACT_V (v[i_4857] , b[i_4857]) } }
#define MULTIPLY_VV(v,b) { F(i_4857, min( SIZE(v) , SIZE(b) ) ){ MULTIPLY_V (v[i_4857] , b[i_4857]) } }
#define DIVIDE_BY_VV(v,b) { F(i_4857, min( SIZE(v) , SIZE(b) ) ){ DIVIDE_BY_V (v[i_4857] , b[i_4857]) } }
#define DIVIDE_BY_VV_LD(v,b) { F(i_4857, min( SIZE(v) , SIZE(b) ) ){ DIVIDE_BY_V_LD (v[i_4857] , b[i_4857]) } }
#define NORMALIZE_VF(v) { float mul = 1./( *max_element(ALL(v)) ); MULTIPLY_ALL_BY(v,mul) }
#define NORMALIZE_VD(v) { double mul = 1./( *max_element(ALL(v)) ); MULTIPLY_ALL_BY(v,mul) }
#define PERCENTAGES_OF_SUM_VF(v) { float mul = 1./( SUM_VF(v) ); MULTIPLY_ALL_BY(v,mul) }
#define PERCENTAGES_OF_SUM_VD(v) { double mul = 1./( SUM_VF(v) ); MULTIPLY_ALL_BY(v,mul) }
#define MIN_MAX(a,b) {if (a > b) swap(a,b);}
#define MAX_2(a,b,c) max(a , b)
#define MAX_3(a,b,c) max(a , max(b,c))
#define MAX_4(a,b,c,d) max(max(a,d) , max(b,c))
#define MAX_5(a,b,c,d,e) max(max(a,d) , MAX_3(b,c,e))
#define MAX_6(a,b,c,d,e,f) max(max(a,b) , MAX_4(c,d,e,f))
#define MIN_2(a,b,c) min(a , b)
#define MIN_3(a,b,c) min(a , min(b,c))
#define MIN_4(a,b,c,d) min(min(a,d) , min(b,c))
#define MIN_5(a,b,c,d,e) min(min(a,b) , MAX_3(c,d,e))
#define MIN_6(a,b,c,d,e,f) min(min(a,b) , MAX_4(c,d,e,f))
#define MAX(...) CONCAT_2(MAX_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define MIN(...) CONCAT_2(MIN_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define POW_2(x) (x*x)
#define POW_3(x) (x*x*x)
struct timeval time_start;
double TIME_SINCE(struct timeval back_then)
{
struct timeval now; gettimeofday(&now, NULL);
return ((now.tv_sec - back_then.tv_sec) * 1000000u +
now.tv_usec - back_then.tv_usec) / 1.e6;
}
random_device rndd;
mt19937 mt_rnd(rndd());
uniform_real_distribution<> zero_to_one_rnd(0.0, 1.0);
template <class T>
void SORT_LARGE_FIRST(vector<T> &v)
{
sort( ALL(v), greater<T>());
}
template <class T>
vector<T> Shuffled_Per_Indices( vector<T> &v, vector<int> &ind )
{
vector<T> nu(
min( SIZE(v), SIZE(ind) )
);
F_all(i, nu)
{
nu = v[ ind[i] ];
}
return nu;
}
template <class T, class U>
vector<T> Split_Pair_0( vector< pair<T,U> > &v )
{
vector<T> nu( SIZE(v) );
F_all(i,v)
{
nu[i] = v[i].A;
}
return nu;
}
template <class T, class U>
vector<U> Split_Pair_1( vector< pair<T,U> > &v )
{
vector<U> nu( SIZE(v) );
F_all(i,v)
{
nu[i] = v[i].B;
}
return nu;
}
template <class T, class U>
vector<T> Split_Tuple( vector< tuple<T,U> > &v , int x ) // x = 0, 1, etc
{
vector<T> nu( SIZE(v) );
F_all(i,v)
{
nu[i] = std::get<x>( v[i] );
}
return nu;
}
template <class T>
vector<T> Split_VV( vector< vector<T> > &v , int n )
{
vector<T> nu( SIZE(v) );
F_all(i,v)
{
nu[i] = v[i][n];
}
return nu;
}
// ranges can be EXTREMELY slow due to VI. Might want to use int[] array.
void Range( VI &rng, int f, int t ) // int range [F , T]. F>T is Okay
{
if (f<=t)
{
rng.resize(t-f+1);
F_I_F_T_UP(i,f,t)
rng[i-f] = i;
}
}
else
{
rng.resize(f-t+1);
F_I_F_T_DOWN(i,f,t)
rng[i-t] = i;
}
}
}
void Range_To_Center( VI &rng, int f, int t ) // int range [F , T]. F<=T
{
rng.resize(t-f+1);
int co;
co = f;
F_I_F_T_S_UP(i,f,t,2)
rng[i-f] = co;
co++;
}
co = t;
F_I_F_T_S_UP(i,f+1,t,2)
rng[i-f] = co;
co--;
}
}
template <class T, class U>
vector<U> SORT_LARGE_FIRST_BY_OTHER_V( vector<U> &v, vector<T> &by_values )
{
vector< pair<T, int> > srt( SIZE(v) );
F_all(i, v)
{
srt[i].A = by_values[i];
srt[i].B = i;
}
SORT_LARGE_FIRST( srt );
vector<U> res( SIZE(v) );
F_all(i, v)
{
res[i] = v[ srt[i].B ];
}
v = res;
return res;
}
template <class T, class U>
vector<U> SORT_SMALL_FIRST_BY_OTHER_V( vector<U> &v, vector<T> &by_values )
{
vector< pair<T, int> > srt( SIZE(v) );
F_all(i, v)
{
srt[i].A = by_values[i];
srt[i].B = i;
}
SORT_SMALL_FIRST( srt );
vector<U> res( SIZE(v) );
F_all(i, v)
{
res[i] = v[ srt[i].B ];
}
v = res;
return res;
}
template <class T>
void SORT_LARGE_FIRST_INDICES_BY_VALUES_FROM_ARRAY( vector<int> &v, vector<T> &by_values )
{
vector< pair<T, int> > srt( SIZE(v) );
F_all(i, v)
{
srt[i].A = by_values[ v[i] ];
srt[i].B = v[i];
}
SORT_LARGE_FIRST( srt );
v = Split_Pair_1(srt);
}
template <class T>
void SORT_SMALL_FIRST_INDICES_BY_VALUES_FROM_ARRAY( vector<int> &v, vector<T> &by_values )
{
vector< pair<T, int> > srt( SIZE(v) );
F_all(i, v)
{
srt[i].A = by_values[ v[i] ];
srt[i].B = v[i];
}
SORT_SMALL_FIRST( srt );
v = Split_Pair_1(srt);
}
template <class T>
T V_Median(vector<T> v)
{
vector<T> x = v;
SORT_SMALL_FIRST(x);
return x[ SIZE(x)/2 ];
}
template <class T>
map<T, int> Count_Occurrences_In_V(vector<T> &v)
{
map<T, int> m;
F_elem(e,v)
{
m[ e ]++;
}
return m;
}
template <class T>
int Count_Occurrences_Of(vector<T> &v, T &x)
{
int s=0;
F_E(v,e)
if(e == x)
s++;
}
return s;
}
template <class T>
vector< pair<T, int> > Add_Index(vector<T> &v)
{
vector< pair<T, int> > nu;
F_all(i,v)
{
nu.PUSH_XX(v[i],i);
}
return nu;
}
template <class T, class U>
vector< pair<T, U> > Combine(vector<T> &a, vector<U> &b)
{
vector< pair<T, U> > nu;
F_all(i,a)
{
nu.PUSH_XX(a[i],b[i]);
}
return nu;
}
template <class T>
void out_line_V(const vector<T> &v, ostream &c = cout)
{
F_all(i,v)
{
c << v[i] << " ";
}
c << END;
}
template <class T>
void out_line_VV(const vector<T> &v, ostream &c = cout)
{
F_all(i,v)
{
out_line_V(v[i], c);
}
c << END;
}
template <class T>
void out_line_VP(const vector<T> &v, ostream &c = cout)
{
F_all(i,v)
{
c << v[i].A << " " << v[i].B << " | ";
}
c << END;
}
// template <class T>
// void out_vals_at_indices(vector<T> &v, VI &ind)
// {
// F_all(i,ind)
// {
// std::cout << v[ ind[i] ] << " ";
// }
// std::cout << END;
// }
void create_folder(string folder_path)
{
string mkdir = "mkdir -p " + folder_path;
system(mkdir.c_str());
}
template <class T>
int count_positive(vector<T> &v)
{
int x=0;
F_E_WHERE(v,e, e>0)
x++;
}
return x;
}
LD dist_3(long double x, long double y, long double z)
{
return sqrt(x*x + y*y + z*z);
}
LD dist_2(long double x, long double y)
{
return sqrt(x*x + y*y);
}
template <typename T,typename U>
std::pair<T,U> operator+(const std::pair<T,U> & l,const std::pair<T,U> & r) {
return {l.first+r.first,l.second+r.second};
}
template <typename T,typename U>
std::pair<T,U> operator-(const std::pair<T,U> & l,const std::pair<T,U> & r) {
return {l.first-r.first,l.second-r.second};
}
template <class T, class S, class C>
S& Container(priority_queue<T, S, C>& q)
{
struct HackedQueue : private priority_queue<T, S, C>
{
static S& Container(priority_queue<T, S, C>& q)
{
return q.*&HackedQueue::c;
}
};
return HackedQueue::Container(q);
}
template<typename T>
void print_queue(T& q)
{
while(!q.empty())
{
std::cout << q.top() << " ";
q.pop();
}
std::cout << '\n';
}
template<typename T>
string V_To_STR(vector<T> & v)
{
string x="";
F_elem(e,v)
{
x += STR(e) + " ";
}
return x;
}
template<typename T>
void out_VP(const T & a)
{
OUT( SIZE(a) )
F_all(i,a)
{
OUT( a[i].A, a[i].B );
}
return;
}
template<typename T>
void out_V(const T &a)
{
COUT( SIZE(a) )
F_all(i,a)
{
OUT( a[i] );
}
return;
}
template<typename T>
void out_VV(const T &a)
{
OUT( SIZE(a) )
F_all(i,a)
{
out_V( a[i] );
}
return;
}
template<class T>
constexpr const T& CLAMP( const T& v, const T& lo, const T& hi )
{
assert( !(hi < lo) );
return (v < lo) ? lo : (hi < v) ? hi : v;
}
template<typename T>
string int_to_str(T i)
{
string x,pre;
if (i==0)
return "0";
if ( i < INT 0)
{
pre = "-";
i = -i;
}
if ( i < INT 0)
{
return "INF";
}
while(i>0)
{
x = CHAR_STR((int)'0' + ( INT i % INT 10)) + x;
i /= 10;
}
return pre+x;
}
template<class T>
vector<vector<T>> transpose(vector<vector<T>> &vv)
{
if (vv.size() == 0)
return vv;
vector<vector<T> > trans_vec(vv[0].size(), vector<T>());
for (int i = 0; i < vv.size(); i++)
{
for (int j = 0; j < vv[i].size(); j++)
{
trans_vec[j].push_back(vv[i][j]);
}
}
return trans_vec;
}
bool smaller_B__pair_int_double (const pair<int,double> &a, const pair<int,double> &b)
{
return ( a.B < b.B ); // smaller
}
bool smaller_B__pair_int_float (const pair<int,float> &a, const pair<int,float> &b)
{
return ( a.B < b.B ); // smaller
}
bool smaller_B__pair_int (const pair<int,int> &a, const pair<int,int> &b)
{
return ( a.B < b.B ); // smaller
}
bool larger_B__pair_int_double (const pair<int,double> &a, const pair<int,double> &b)
{
return ( a.B > b.B ); // larger
}
bool larger_B__pair_int_float (const pair<int,float> &a, const pair<int,float> &b)
{
return ( a.B > b.B ); // larger
}
bool larger_B__pair_int (const pair<int,int> &a, const pair<int,int> &b)
{
return ( a.B > b.B ); // larger
}
bool larger_B__pair_P_II_int (const pair<P_II,int> &a, const pair<P_II,int> &b)
{
return ( a.B > b.B ); // larger
}
// public static int[] merge(int[] a, int[] b) {
// int[] answer = new int[a.length + b.length];
// int i = 0, j = 0, k = 0;
// while (i < a.length && j < b.length)
// answer[k++] = a[i] < b[j] ? a[i++] : b[j++];
// while (i < a.length)
// answer[k++] = a[i++];
// while (j < b.length)
// answer[k++] = b[j++];
// return answer;
// }
template<typename T>
void insert_val_in_sorted_v(T x, vector<T> &v)
{
if ( !SZ(v) )
{
v.PUSH(x);
return;
}
int larger = UP_BOUND_I(v,x);
v.resize( SZ(v) +1 );
F_I_F_T_DOWN(i, SZ(v)-2, larger)
v[i+1] = v[i];
}
v[larger] = x;
}
template<typename T>
int Count_Intersection(const vector<T> &a, const vector<T> &b)
{
vector<T> c( min( SZ(a), SZ(b) ) );
typename vector<T>::iterator it;
it = set_intersection(ALL(a),ALL(b),c.begin());
return it - c.begin();
}
template<typename T>
vector<T> Intersection(const vector<T> &a, const vector<T> &b)
{
vector<T> c( min(SZ(a), SZ(b)) );
typename vector<T>::iterator it;
it = set_intersection(ALL(a),ALL(b),c.begin());
c.resize(it - c.begin());
return c;
}
LD SQRT2 = sqrt(2);
LD SQRT3 = sqrt(3);
LD SQRT5 = sqrt(5);
VLD SQRT={0};
void pregenerate_SQRT(int x=5000)
{
SQRT.resize(x+1);
F_I_F_T(i,1,x)
SQRT[i] = sqrt(i);
}
}
VI AROUND_4X = {0,0 ,1,-1};
VI AROUND_4Y = {-1,1 ,0,0};
VP_II AROUND_4PXY = {{0,-1},{0,1} ,{1,0},{-1,0}};
// F_E(AROUND_4PXY , aro)
// int n_x = CLAMP( aro.A + x , 0 , m_width - 1 );
// int n_y = CLAMP( aro.B + y , 0 , m_height- 1 );
// }
VI AROUND_9X = {0,0 ,1,-1 ,1,-1 ,-1,1};
VI AROUND_9Y = {-1,1 ,0,0 ,1,-1 ,1,-1};
VP_II AROUND_9PXY = {{0,-1},{0,1} ,{1,0},{-1,0}, {1,-1},{-1,1} ,{1,1},{-1,-1}};
float I_MEASURE_TIME=0.;
const float MAX_TIME_ON_RND_TRY =0.5;
const int MAX_RND_TRY_ITER =1500;
#define return_type pair< pair<vector<string> , VP_II>, P_DD >
return_type best_sol({{VS(), {}}, {2.,1.} }); // {final rect, coords}, {Error_Score, Compression_Score}
vector< vector<string> > grids;
int maxHeight;
int maxWidth;
int minHeight;
int minWidth;
int overall_iterations=0;
int N_rects;
int T_total_px = 0;
float tot_px_div_by_rect;
double P;
VVVI G; // { [y][x][i] }
vector< pair<VVI, int> > pics;
float rev_p;
float p_tot_px;
float val_per_tile;
int result_H;
int result_W;
string stats_file_name="";
VI vi_stat_key, vi_stat_val;
int stat_at_least_this_many_outs;
int stat_a_bit_more_outs;
VVP_FF calculated_errors (90, VP_FF(90,{-1.,-1.}));
VP_II previously_calculated_resolutions;
int mids[128][128][2]={};
int mids_transposed[128][128][2]={};
// For continuation
vector< vector< pair<VVVI, VP_II> >> previously_calculated(128, vector< pair<VVVI, VP_II> >(128)); // -> G, coords
VP_II candidates;
float candidate_scores[128][128][5]; // [y][x][ min, max, compression, est, est improvement vs best_sol ]
float exploration_level; // Has effect on level of exploration vs exploitation
const float exploit_after = 2.;
void propagate_max_expected_error(int x, int y, float err, float time_invested)
{
if( calculated_errors[y][x].A < 0. )
{
calculated_errors[y][x] = {err, time_invested};
previously_calculated_resolutions.PUSH({x,y});
}
else
calculated_errors[y][x] = {err, time_invested + calculated_errors[y][x].B };
}
float candidate_est_score(float min_score_after_sec, float max_score_after_sec, float confidence)
{ // lower -> better
float diff = (max_score_after_sec - min_score_after_sec);
// return min_score_after_sec + diff*( ( 1. - confidence) * exploration_vs_exploitation );
return max_score_after_sec - diff * confidence;
}
bool res_makes_no_sense(int x, int y)
{
float prev_record = best_sol.B.A + best_sol.B.B;
int area = x*y;
float max_full_compression_error = 0.49;
float linelikeness = (float)max(x,y) / (float)min(x,y);
if (area<300)
return 0;
if (
(
x>=20 && y>=20
&& x+3 < y // don't do large mirror versions
)
||
(
T_total_px > 500
&&
linelikeness >= 2.5 // Wide side >=3.5x Narrow side length
)
||
(
T_total_px > 1100
&&
linelikeness >= 2.2 // Wide side >=3.5x Narrow side length
)
||
linelikeness >= 3 // Wide side >=3.5x Narrow side length
||
prev_record <= p_tot_px * area
|| (
P<0.21
&&
(
(float)T_total_px / (float)max(350,area) > 2.2
||
(
N_rects > 40
&&
(float)T_total_px / (float)max(350,area) > 1.8 // compressed by > X times
)
)
)
|| (
P<0.11
&&
(
(float)T_total_px / (float)max(350,area) > 1.5 // compressed by > X times
||
(
N_rects > 50
&&
(float)T_total_px / (float)max(350,area) > 1.3 // compressed by > X times
)
)
)
)
return 1;
return 0;
}
int a_b_who_has_smaller_error(int aX, int aY, int Bx, int By, int inside=0) // -1 is A has smaller error / 0 is unknown / 1 if B has smaller error
{
int aSx= maxWidth + aX;
int aSy= maxHeight + aY;
int bSx= maxWidth + Bx;
int bSy= maxHeight + By;
float A_area = aSx * aSy;
float B_area = bSx * bSy;
int dx = Bx - aX;
int dy = By - aY;
if ( // B is bigger. B expected to have a SMALLER error. MAX_ERROR LOWER or same
(Bx >= aX && By >= aY)
|| (
A_area*1.3 < B_area
&& Bx >= min(aX, 5)
&& By >= min(aY, 5)
)
|| (
A_area*1.2 < B_area
&& Bx >= min(aX, 10)
&& By >= min(aY, 10)
)
|| (
A_area*1.1 < B_area
&& Bx >= min(aX, 20)
&& By >= min(aY, 20)
)
)
return 1;
if(!inside)
{
return - a_b_who_has_smaller_error(Bx, By, aX, aY, 1);
}
return 0;
}
VF estimate_resolution(int dW, int dH) // -> {lower error case, slightly more "realistic" error case}
{
float result_H = maxHeight +dH;
float result_W = maxWidth +dW;
if(res_makes_no_sense(result_W, result_H))
return {-1};
float area = result_H*result_W;
float compression_score = p_tot_px * area;
// float box_bonus = (max(result_H,result_W) / min(result_H,result_W) -1.) * 0.001; // Less square-like -> less sexy
float min_error=0., max_error=0.5;
float confidence_level = 0.;
F_I_PE(previously_calculated_resolutions, i, bx, by)
// int bx = b.A;
// int by = b.B;
float b_w = maxWidth + bx;
float b_h = maxHeight + by;
float b_area = b_w * b_h;
float b_err = calculated_errors[by][bx].A;
int b_has_smaller_error = a_b_who_has_smaller_error(dW, dH, bx, by);
if (b_has_smaller_error == 1) // a has larger error. (A is smaller in size)
{
MAXIMIZE(min_error, (float)(b_err) )
MAXIMIZE(max_error, (float)(b_err*1.05) )
}
else
if (b_has_smaller_error == -1) // a has smaller error. (A is larger in size)
{
MINIMIZE(max_error, float(b_err*0.98))
MINIMIZE(min_error, float(b_err*0.8))
}
if (b_has_smaller_error != 0)
{
double confy = min( area, b_area ) / max( area, b_area );
confy *= confy*confy*confy*confy;
confy *= confy;
confidence_level += confy*0.001;
MAXIMIZE(confidence_level, float(confy*0.8) )
MINIMIZE(confidence_level, (float)0.9 )
}
if (
bx == dW
&& by == dH
)
{
max_error = b_err;
min_error = b_err*0.95;
confidence_level = 1.;
break;
}
}
return {compression_score + min_error, compression_score + max_error, compression_score, confidence_level}; // {min, max, compression}
}
void find_good_candidates()
{
candidates.resize(0);
exploration_level = max(1. - (TIME_SINCE(time_start)/exploit_after) , 0.); // ~1 -> explore, later, ~0 -> exploit
F(85,y)
F(85,x)
if (calculated_errors[y][x].A > -1)
continue;
VF est = estimate_resolution(x,y);
if (est[0] < 0)
continue;
float min_est = est[0];
float max_est = est[1];
float cmp_est = est[2];
float confidence = est[3];
float est_score = candidate_est_score(min_est, max_est, confidence);
if ( // if can generate a decent improvement vs our current best_sol
est_score < (best_sol.B.A + best_sol.B.B)*0.997
)
{
candidate_scores[y][x][0] = min_est;
candidate_scores[y][x][1] = max_est;
candidate_scores[y][x][2] = cmp_est;
candidate_scores[y][x][3] = est_score;
candidate_scores[y][x][4] = (best_sol.B.A + best_sol.B.B) / est_score; // >1. More -> better candidate
candidates.PUSH({x,y});
}
}
}
VF est_actual;
// est_actual = estimate_resolution(5,3);
// CERR(COL_Y+"ACTUAL BEST HAS THESE NUMBERS")
// out_line_V(est_actual, cerr);
est_actual = estimate_resolution(10,4);
CERR(COL_Y+"ACTUAL BEST HAS THESE NUMBERS")
// out_line_V(est_actual, cerr);
// est_actual = estimate_resolution(5,4);
// CERR(COL_Y+"NEXT HAS THESE NUMBERS")
// out_line_V(est_actual, cerr);
}
P_II which_candidate_trims_most()
{ // Takes into account these things:
// SUM of [i](expected candidate i'th score difference / new_best_score)
// == expected score change (based on error change) in C2 in other candidate after C1 found to have est error
//
CERR("Processing candidates", SZ(candidates))
if(!SZ(candidates))
{
CERR("DONT HAVE ANY CANDS")
return {-1,-1};
}
int max_area_of_candidate_seen =-1;
int max_area_x =-1;
int max_area_y =-1;
float most_utility = -1.;
P_II best_c={-1,-1};
F_E(candidates, c)
float u = 0.;
int x = c.A;
int y = c.B;
int c_W = maxWidth + x;
int c_H = maxHeight + y;
IF_MORE_UPDATE (
max_area_of_candidate_seen
, c_H*c_W
, max_area_x
, c_W
, max_area_y
, c_H
)
float c_max_score = candidate_scores[y][x][1];
float c_cmp = candidate_scores[y][x][2];
float assumed_new_best = candidate_scores[y][x][3];
float c_score_decrease_level = candidate_scores[y][x][4]; // >1. Higher -> better. Reverse to what's in final score
float c_appeal = c_score_decrease_level * c_score_decrease_level * c_score_decrease_level;// higher -> better candidate.
float c_est_ERROR = assumed_new_best - c_cmp;
float sum_of_impact = 0.; // sum abs appeal difference calculating this candidate is expected to make on all candidates, himself included.
F_E(candidates, C2)
// Will raise c2's expected min_error_score if // area // coords // of c2 > that of c1.
int X2 = C2.A;
int Y2 = C2.B;
int dx = X2 - x;
int dy = Y2 - y;
if( abs(dy) + abs(dx) >5 )
continue;
int C2_w = X2 + maxWidth;
int C2_h = Y2 + maxHeight;
float C2_cmp = candidate_scores[Y2][X2][2];
float C2_min_SCORE = candidate_scores[Y2][X2][0];
float C2_max_SCORE = candidate_scores[Y2][X2][1];
float C2_est_SCORE = candidate_scores[Y2][X2][2];
// float C2_new_min_ERROR;
// float C2_new_max_ERROR;
// float C2_min_ERROR = C2_new_min_ERROR = C2_min_SCORE - C2_cmp;
// float C2_max_ERROR = C2_new_max_ERROR = C2_max_SCORE - C2_cmp;
float C2_min_ERROR = C2_min_SCORE - C2_cmp;
float C2_max_ERROR = C2_max_SCORE - C2_cmp;
float C2_score_decrease_level = candidate_scores[y][x][4];
float C2_appeal = C2_score_decrease_level ;// higher -> better candidate.
int C2_has_smaller_error = a_b_who_has_smaller_error(x,y, X2, Y2);
float error_diff = 0.;
if (C2_has_smaller_error == 0)
continue;
else
if ( // Candidate B is larger -> has less errors
c_est_ERROR
< C2_max_ERROR
&&
C2_has_smaller_error == 1
)
{
error_diff += C2_max_ERROR - c_est_ERROR;
if (
c_est_ERROR
< C2_min_ERROR
)
error_diff += C2_min_ERROR - c_est_ERROR;
}
else
if ( // Candidate B is smaller -> has more errors
c_est_ERROR
> C2_min_ERROR
&&
C2_has_smaller_error == -1
)
{
error_diff += C2_min_ERROR - c_est_ERROR;
if (
c_est_ERROR
< C2_max_ERROR
)
error_diff += C2_max_ERROR - c_est_ERROR;
}
sum_of_impact += C2_appeal * ( error_diff/C2_max_SCORE );
}
// u = sum_of_impact * exploration_level + (2.2-exploration_level)*c_appeal;
u = sum_of_impact;
// u = c_appeal;
// u = 2.-c_max_score;
// CERR("which_candidate_trims_most:", STR(c_W) +"x"+ STR(c_H), "utility", (int)(u*1000.))
IF_MORE_UPDATE (
most_utility
, u
, best_c
, c
)
}
if(best_c.A == -1)
{
CERR(COL_R_BG+ "No good candidate found. WTF?! BUUUUG!")
best_c.A = SZ(best_sol.A.A[0]);
best_c.B = SZ(best_sol.A.A);
}
CERR("max_area_of_candidate_seen", max_area_of_candidate_seen, STR(max_area_x) +"x"+ STR(max_area_y))
VF est_actual;
est_actual = estimate_resolution(best_c.A,best_c.B);
CERR(COL_Y+"Here's how we estimated this `best` position")
out_line_V(est_actual, cerr);
return best_c;
}
P_II get_res_with_top_potential()
{
find_good_candidates();
P_II XY = which_candidate_trims_most();
int x = XY.A;
int y = XY.B;
// CERR("ASD")
if (x<0)
return {-1,-1};
// CERR("POIPO")
float min_score = candidate_scores[y][x][0];
float max_score = candidate_scores[y][x][1];
float est_score = candidate_scores[y][x][3];
CERR(COL_G_BG + " " + STR(XY.A) +" "+ STR(XY.B) + " Resolution chosen for exploration. Expecting score between ", min_score, max_score, est_score)
// CERR("ODSP")
return XY;
}
P_DD score_strings(VVS &grids, VS sol, VP_II &coord)
{
int diff=0;
F_I_PE(coord, i, x,y)
F_I_E(grids[i], dy, x_line)
F_I_E(x_line, dx, ch)
diff += abs( ch - sol[y+dy][x+dx] );
}
}
}
// res = (float)diff / ( (float)T_total_px * 12.5);
// cerr <<"avg error "<<res<<END;
// cerr <<"score "<<res<<END;
return {
rev_p * (float)diff // Error
, p_tot_px* (float)SZ(sol) * (float)SZ(sol[0]) // Compression
};
}
pair<float,int> score_G(VVVI &G, int x=0, int y=0, int dx=-1, int dy=-1)
{
if (dx == -1)
{
dx = SZ(G[0])-x;
dy = SZ(G) -y;
}
int diff=0;
F_I_F_T_UP( YY, y, y+dy-1)
F_I_F_T_UP( XX, x, x+dx-1)
int siz = SZ(G[YY][XX]);
if(!siz)
continue;
int upper_med = G[YY][XX][ siz/2 ];
F_E( G[YY][XX], e)
diff += abs( upper_med - e );
}
}
}
return {
rev_p * (float)diff // Error calc
, diff
};
}
void add_to_G(VVI &what, int x, int y, P_II &coord)
{
F_I_E(what, yy, line)
F_I_E(line, xx, val)
insert_val_in_sorted_v(val, G[y+yy][x+xx]);
}
}
coord = {x,y};
}
void remove_from_G(VVI &what, P_II &coord)
{
int x=coord.A;
int y=coord.B;
F_I_E(what, yy, line)
F_I_E(line, xx, val)
REMOVE_VALUE(G[y+yy][x+xx], val);
}
}
coord = {-1,-1};
}
float edging_negative(VVI &what, int xx=0, int yy=0, int leave_min_H=1, int leave_min_W=1)
{ // How many empty points did we isolate around the edges?
// MAXIMIZE(leave_min_H, minHeight);
// MAXIMIZE(leave_min_W, minWidth);
// if(SZ(grids)>60 && P<0.1)
// {
// MAXIMIZE(leave_min_H, 7);
// MAXIMIZE(leave_min_W, 7);
// }
// else
// if(SZ(grids)>50 || P<0.12)
// {
// MAXIMIZE(leave_min_H, 6);
// MAXIMIZE(leave_min_W, 6);
// }
// else
// if(P<0.25)
// {
// MAXIMIZE(leave_min_H, 5);
// MAXIMIZE(leave_min_W, 5);
// }
int sx= SZ(what[0]);
int sy= SZ(what);
int mx_x= SZ(G[0]);
int mx_y= SZ(G);
int cur_count;
// int last_fail=-1;
float fucked_up=0.;
float final_edge_bonus=0.1;
bool limited_by_edge;
int XXYY;
int till;
int empty;
int L_edge_open, R_edge_open, T_edge_open, B_edge_open, edge_open;
float add_const=2.;
// #define funk(c) -(float)SQRT[c]/2.
#define funk(c) 0
XXYY = yy-leave_min_H;
till = max(0, XXYY);
limited_by_edge = till > XXYY;
cur_count = 0;
edge_open = 0;
F_I_F_T_UP(x, xx, xx+sx-1 ) // top border
if (cur_count)
edge_open += add_const;
// if (cur_count && cur_count < leave_min_H)
// {
// fucked_up += funk(cur_count)* (1.+ limited_by_edge * final_edge_bonus);
// }
cur_count=0;
empty = !SZ(G[yy][x]);
if (!empty)
continue;
F_I_F_T_DOWN(y, yy-1, till)
empty = !SZ(G[y][x]);
if (empty)
cur_count++;
else
break;
}
}
T_edge_open = edge_open;
XXYY = yy+sy+leave_min_H-1;
till = min(mx_y-1, XXYY);
limited_by_edge = till < XXYY;
cur_count = 0;
edge_open = 0;
F_I_F_T_UP(x, xx, xx+sx-1 ) // bottom border
if (cur_count)
edge_open += add_const;
// if (cur_count && cur_count < leave_min_H)
// {
// fucked_up += funk(cur_count)* (1.+ limited_by_edge * final_edge_bonus);
// }
cur_count=0;
empty = !SZ(G[yy+sy-1][x]);
if (!empty)
continue;
F_I_F_T_UP( y, yy+sy, till)
empty = !SZ(G[y][x]);
if (empty)
cur_count++;
else
break;
}
}
B_edge_open = edge_open;
XXYY = xx-leave_min_W;
till = max(0, XXYY);
limited_by_edge = till > XXYY;
cur_count = 0;
edge_open = 0;
F_I_F_T_UP(y, yy, yy+sy-1 ) // left border
if (cur_count)
edge_open += add_const;
// if (cur_count && cur_count < leave_min_W)
// {
// fucked_up += funk(cur_count)* (1.+ limited_by_edge * final_edge_bonus);
// }
cur_count=0;
empty = !SZ(G[y][xx]);
if (!empty)
continue;
F_I_F_T_DOWN(x, xx-1, till)
empty = !SZ(G[y][x]);
if (empty)
cur_count++;
else
break;
}
}
L_edge_open = edge_open;
XXYY = xx+sx+leave_min_W-1;
till = min(mx_x-1, XXYY);
limited_by_edge = till < XXYY;
cur_count = 0;
edge_open = 0;
F_I_F_T_UP(y, yy, yy+sy-1 ) // right border
if (cur_count)
edge_open += add_const;
// if (cur_count && cur_count < leave_min_W)
// {
// fucked_up += funk(cur_count)* (1.+ limited_by_edge * final_edge_bonus);
// }
cur_count=0;
empty = !SZ(G[y][xx+sx-1]);
if (!empty)
continue;
F_I_F_T_UP( x, xx+sx, till)
empty = !SZ(G[y][x]);
if (empty)
cur_count++;
else
break;
}
}
R_edge_open = edge_open;
// fucked_up = 0;
int TL, TR, BL, BR;
TL = TR = BL = BR = 0;
// TL
int emptyTL = !SZ(G[yy][xx]);
int emptyTLT=0, emptyTLL=0;
if(xx > 0)
emptyTLL = !SZ(G[yy][xx-1]);
if(yy > 0)
emptyTLT = !SZ(G[yy-1][xx]);
// TR
int emptyTR = !SZ(G[yy][xx+sx-1]);
int emptyTRT=0, emptyTRR=0;
if(xx+sx < mx_x)
emptyTRR = !SZ(G[yy][xx+sx]);
if(yy > 0)
emptyTRT = !SZ(G[yy-1][xx+sx-1]);
// BR
int emptyBR = !SZ(G[yy+sy-1][xx+sx-1]);
int emptyBRB=0, emptyBRR=0;
if(xx+sx < mx_x)
emptyBRR = !SZ(G[yy+sy-1][xx+sx]);
if(yy+sy < mx_y)
emptyBRB = !SZ(G[yy+sy][xx+sx-1]);
// BL
int emptyBL = !SZ(G[yy+sy-1][xx]);
int emptyBLB=0, emptyBLL=0;
if(xx > 0)
emptyBLL = !SZ(G[yy+sy-1][xx-1]);
if(yy+sy < mx_y)
emptyBLB = !SZ(G[yy+sy][xx]);
TL = emptyTL * (emptyTLT * emptyTLL + emptyTLT + emptyTLL);
TR = emptyTR * (emptyTRT * emptyTRR + emptyTRT + emptyTRR);
BR = emptyBR * (emptyBRB * emptyBRR + emptyBRB + emptyBRR);
BL = emptyBL * (emptyBLB * emptyBLL + emptyBLB + emptyBLL);
int side_qual = TL + TR + BR + BL;
// CERR( "side", side_qual * 3, "edge_opens", L_edge_open + R_edge_open + T_edge_open + B_edge_open)
fucked_up += side_qual * 1;
fucked_up += L_edge_open + R_edge_open + T_edge_open + B_edge_open;
fucked_up*=0.5;
return fucked_up;
}
/*
int edging_good(VVI &what, int xx=0, int yy=0, int left_min_H=4, int left_min_W=4)
{ // Compensate for the holes we filled.
MAXIMIZE(left_min_H , minHeight);
MAXIMIZE(left_min_W , minWidth );
int sx= SZ(what[0]);
int sy= SZ(what);
if(left_min_H)
F_I_F_T(x, xx-1, xx+sx) // top line
if(x<1)
{
}
}
}
*/
int qwe=0;
int prb_vx[10];
int prb_vy[10];
__attribute__((optimize("-ffast-math")))
VI probe_diff_G(int (*what), int shift, int sx, int sy, int x=0, int y=0, float past_best=BILL, float freeplace_sum_coef=0.)
{
int diff=0;
int free_places_lost=0;
int max_diff=BILL;
// float max_diff=BILL;
int w_size = sx*sy;//SZ(what) * SZ(what[0]);
if (P<0.6)
{
if (N_rects>25)
{
if(w_size>85)
max_diff = ceil(val_per_tile * 1.35 * w_size);
else
if(w_size>75)
max_diff = ceil(val_per_tile * 1.4 * w_size);
else
if(w_size>60)
max_diff = ceil(val_per_tile * 1.45 * w_size);
else
if(w_size>50)
max_diff = ceil(val_per_tile * 1.5 * w_size);
else
if(w_size>35)
max_diff = ceil(val_per_tile * 1.6 * w_size);
else
if(w_size>25)
max_diff = ceil(val_per_tile * 1.7 * w_size);
else
if(w_size>20)
max_diff = ceil(val_per_tile * 1.8 * w_size);
}
else
if (N_rects>=20)
{
if(w_size>85)
max_diff = ceil(val_per_tile * 1.7 * w_size);
else
if(w_size>75)
max_diff = ceil(val_per_tile * 1.8 * w_size);
else
if(w_size>60)
max_diff = ceil(val_per_tile * 2 * w_size);
}
}
max_diff = min(max_diff, (int)past_best);
int int_freeplace_sum_coef = freeplace_sum_coef;
if (
tot_px_div_by_rect
< 1.5
)
{
if (sx>=sy)
{
F(sy, yy)
F(sx, xx)
int val = what[(yy << shift) + xx];
int YY = yy + y;
int XX = xx + x;
int a = mids[YY][XX][0];
int b = mids[YY][XX][1];
if (b == -1)
{
free_places_lost++;
continue;
}
if (a == -1)
{
diff += abs(val - b);
}
else
{
if (a <= val && val <= b) // becomes new medium O O ^ O O
{
continue;
}
else
{
diff += min( abs(a - val), abs(b - val) );
}
}
}
if (
diff
+ free_places_lost * int_freeplace_sum_coef
// + free_places_lost * freeplace_sum_coef
// cur_score
> max_diff
)
return {MIL, w_size};
}
}
else
{
F(sx, xx)
F(sy, yy)
int val = what[(xx << shift) + yy];
int YY = yy + y;
int XX = xx + x;
int a = mids_transposed[XX][YY][0];
int b = mids_transposed[XX][YY][1];
if (b == -1)
{
free_places_lost++;
continue;
}
if (a == -1)
{
diff += abs(val - b);
}
else
{
if (a <= val && val <= b) // becomes new medium O O ^ O O
{
continue;
}
else
{
diff += min( abs(a - val), abs(b - val) );
}
}
}
if (
diff
+ free_places_lost * int_freeplace_sum_coef
> max_diff
)
return {MIL, w_size};
}
}
}
else
{
if (sx>=sy)
{
F(sy, yy)
F(sx, xx)
int val = what[(yy << shift) + xx];
int YY = yy + y;
int XX = xx + x;
int a = mids[YY][XX][0];
int b = mids[YY][XX][1];
if (b == -1)
{
free_places_lost++;
continue;
}
if (a == -1)
{
diff += abs(val - b);
}
else
{
if (a <= val && val <= b) // becomes new medium O O ^ O O
{
continue;
}
else
{
diff += min( abs(a - val), abs(b - val) );
}
}
}
}
}
else
{
F(sx, xx)
F(sy, yy)
int val = what[(xx << shift) + yy];
int YY = yy + y;
int XX = xx + x;
int a = mids_transposed[XX][YY][0];
int b = mids_transposed[XX][YY][1];
if (b == -1)
{
free_places_lost++;
continue;
}
if (a == -1)
{
diff += abs(val - b);
}
else
{
if (a <= val && val <= b) // becomes new medium O O ^ O O
{
continue;
}
else
{
diff += min( abs(a - val), abs(b - val) );
}
}
}
}
}
}
return { diff, free_places_lost };
}
VVI VS_to_numbers(VS &a)
{
VVI r( SZ(a), VI( SZ(a[0]), 0 ));
F_I_E(a, y, line)
F_I_E(line, x, ch)
r[y][x] = ch - 'A';
}
}
return r;
}
VS G_to_VS()
{
VS r;
F_I_E(G, y, line)
r.PUSH( string("") );
F_I_E(line, x, vals)
if( SZ(vals) )
r[y] += char('A' + vals[ SZ(vals)/2 ] );
// r[y] += char('M');
else
r[y] += '-';
}
}
return r;
}
void prepare_mids()
{
F(result_H,y)
F(result_W,x)
int siz = SZ(G[y][x]);
mids[y][x][0] = -1;
mids[y][x][1] = -1;
if (siz > 0)
{
mids[y][x][1] = {G[y][x][ siz/2 ]}; // upper mid. Note .B
if (siz%2 == 0)
{
mids[y][x][0] = {G[y][x][ siz/2 -1 ]}; // lower mid. Note .A
}
}
}
}
F(result_H,x)
F(result_W,y)
int siz = SZ(G[x][y]);
mids_transposed[y][x][0] = -1;
mids_transposed[y][x][1] = -1;
if (siz > 0)
{
mids_transposed[y][x][1] = {G[x][y][ siz/2 ]}; // upper mid. Note .B
if (siz%2 == 0)
{
mids_transposed[y][x][0] = {G[x][y][ siz/2 -1 ]}; // lower mid. Note .A
}
}
}
}
}
VP_II find_best_place_for_pic(VVI &p, float edging_coef=1., float free_places_coef=1., int prev_x=-1, int prev_y=-1)
{
int sx = SZ(p[0]);
int sy = SZ(p);
// int p_array[16][16];
int shift;
int* p_array=NULL;
if(sx >= sy)
{
if (sx>8)
shift = 4;
else
if (sx>4)
shift = 3;
else
if (sx>2)
shift = 2;
else
if (sx==2)
shift = 1;
p_array = new int[sy << shift];
F_I_E(p,y,l)
F_I_E(l,x,e)
p_array[(y<<shift) + x] = e;
// p_array[(y*sx) + x] = e;
}
}
}
else // Transposed
{
if (sy>8)
shift = 4;
else
if (sy>4)
shift = 3;
else
if (sy>2)
shift = 2;
else
if (sy==2)
shift = 1;
p_array = new int[sx << shift];
F(sy,y)
F(sx,x)
p_array[(x<<shift) + y] = p[y][x];
}
}
}
VP_II best_place(1,{0,0});
// return best_place;
float least_diff = BILL;
int brk=0;
VI probed;
float probed_val;
float freeplace_sum_coef = free_places_coef * val_per_tile;
prepare_mids();
if (prev_x>-1)
{
probed = probe_diff_G( p_array, shift, sx,sy, prev_x,prev_y );
probed_val = probed[0];
probed_val += freeplace_sum_coef * (float)probed[1];
if (
tot_px_div_by_rect < 4.
)
{
probed_val += edging_coef
* (float)edging_negative(p, prev_x, prev_y)
* val_per_tile
* 0.7;
}
best_place = VP_II(1, {prev_x, prev_y});
least_diff = probed_val;
}
F( 1+ result_H - SZ(p) , y)
F( 1+ result_W - SZ(p[0]) , x)
if (x == prev_x && y == prev_y)
continue;
probed = probe_diff_G( p_array, shift, sx,sy, x,y, least_diff, freeplace_sum_coef );
probed_val = probed[0];
probed_val += freeplace_sum_coef * (float)probed[1]; // free_places_lost
if (
probed_val
<= least_diff
) // Interesting. Lets examine this option closer.
{
if (
tot_px_div_by_rect < 4.
)
{
probed_val += edging_coef
* (float)edging_negative(p, x,y)
* val_per_tile
* 0.7;
}
}
if (
probed_val*1.000001
< least_diff
)
{
least_diff = probed_val;
best_place = VP_II(1,{x,y});
}
else
if (
probed_val*0.99999
< least_diff
)
{
best_place.PUSH({x,y});
}
if(least_diff < 0.000001) // Early stopping
{
brk=1;
break;
}
}
if(brk)
break;
}
delete[] p_array;
return best_place;
}
pair<int, VI> build_a_wall(VP_II &parts, int len)
{
VVI dyn(len+1);
F_E(parts, p)
int l = p.A;
F_I_F_T_DOWN(i, len -l, 0)
if (
(i==0 || SZ(dyn[i]))
&& EMT(dyn[i+l])
)
{
dyn[i+l] = dyn[i];
dyn[i+l].PUSH( p.B );
}
}
if(SZ(dyn[len]))
{
return {-1, dyn[len]};
}
}
F_I_F_T_DOWN(i, len, 0)
if(SZ(dyn[i]))
return {i, dyn[i]};
}
return {0, {}};
}
return_type findSolution(float time_given=0.05, int pW=0, int pH=0, int ultimate=0, int force=0, int try_wall=0, int zero_start=0)
{
result_H = maxHeight +pH;
result_W = maxWidth +pW;
int sol_area = result_H * result_W;
tot_px_div_by_rect = (float)T_total_px / (float)sol_area;
if(!force)
{
if (res_makes_no_sense(result_W,result_H))
{
CERR( "findSolution says this res makes no sense..", STR(result_W) +"x"+ STR(result_H) )
return_type empty_ret;
empty_ret.B={10.,10.};
return empty_ret;
}
}
struct timeval sol_time_start, iter_start_time;
TIME(sol_time_start);
VF freedom;
VP_II coord( SZ(grids), {-1,-1} ), best_coord;
vector<string> out, best_out;
float best_score = BILL;
P_DD pdd;
float time_left_since_start_if_ultimate = 9.75 - TIME_SINCE(time_start);
float time_left_since_start = time_given - TIME_SINCE(sol_time_start);
TIME(iter_start_time);
int rnd_iter=0;
VVVI past_G;
VP_II past_G_coord;
if( SZ(previously_calculated[pW][pH].A) )
{
past_G = previously_calculated[pW][pH].A;
past_G_coord= previously_calculated[pW][pH].B;
G = past_G;
coord = past_G_coord;
}
else
{
G.assign( result_H , VVI( result_W , VI(0) ) );
F_I_PE(pics, i, g, ith)
freedom.PUSH (
(float)SZ(g) *
(float)SZ(g[0])
+ (float)SZ(g)*0.001
// *SQRT[max (
// SZ(g)
// ,
// SZ(g[0])
// )]
);
}
SORT_LARGE_FIRST_BY_OTHER_V( pics, freedom );
VVP_II candidates(11);
if(try_wall)
{
// BUILD TOP
// GET candidates
F_I_PE(pics, i, p, ith)
int px = SZ(p[0]);
int py = SZ(p);
if(coord[ith].A == -1)
candidates[py].PUSH({px,i});
}
F_I_F_T_DOWN(c, 10,4)
pair<int, VI> build = build_a_wall(candidates[c], result_W);
if(build.A == -1)
{
int bsz = SZ(build.B);
if(bsz>=4)
{
swap(build.B[1], build.B[2] );
swap(build.B[2], build.B[ bsz-1 ] );
swap(build.B[ bsz-3 ], build.B[ bsz-2 ] );
}
else
if(bsz>2)
swap(build.B[1], build.B[ bsz-1 ]);
int cur_x=0;
F_E(build.B, i)
int ith = pics[i].B;
add_to_G(pics[i].A, cur_x, 0, coord[ith]);
cur_x += SZ(pics[i].A[0]);
}
break;
}
}
}
// CERR("PLACING PICS")
F_I_PE(pics, i, p, ith)
// CERR(SZ(p)*SZ(p[0]))
int best_x, best_y=best_x=0;
if(i>0 && coord[ith].A==-1)
{
if(!zero_start)
{
VP_II bst = find_best_place_for_pic(p, 1, 1);
int rnd = rand() % SZ(bst);
best_x = bst[rnd].A;
best_y = bst[rnd].B;
}
else
best_x = best_y = 0;
}
// coord[ith] = { best_x, best_y };
// CERR("best_x, best_y",best_x, best_y)
// CERR("p",SZ(p),SZ(p[0]))
add_to_G(p, best_x, best_y, coord[ith]);
}
// CERR("PLACED")
SHUFFLE(pics)
}
// vector< pair<VVI, int> > past_G_pics;
while (
1
// rnd_iter == 0
// ||
// (
// ultimate
// &&
// TIME_SINCE(time_start) < 9.75
// )
// ||
// (
// TIME_SINCE(sol_time_start) < MAX_TIME_ON_RND_TRY
// TIME_SINCE(iter_start_time) < MAX_TIME_ON_RND_TRY
// &&
// (
// force
// ||
// (
// rnd_iter < MAX_RND_TRY_ITER
// &&
// TIME_SINCE(time_start) < 9.1
// )
// )
// )
)
{
float percent_left = TIME_SINCE(iter_start_time) / time_left_since_start;
float exp;
if (ultimate)
{
percent_left = TIME_SINCE(iter_start_time) / time_left_since_start_if_ultimate;
}
if (P<0.2)
percent_left *= 0.2;
exp = percent_left * 5
+ 1.1;
// exp *= exp;
// CERR(SZ(pics), SZ(pics) / exp)
F(4,doitagain)
// TODO: TEST WITH AND WITHOUT
int last_iter_bonus = 0;
if(doitagain == 3)
last_iter_bonus = 5;
// if((doitagain==2) && RND_CHANCE<0.2)
// continue;
// if(doitagain==0 && RND_CHANCE<0.05)
// {
// freedom.resize(0);
// F_I_PE(pics, i, g, ith)
// freedom.PUSH (
// (float)SZ(g) *
// (float)SZ(g[0])
// );
// }
// // SORT_LARGE_FIRST_BY_OTHER_V( pics, freedom );
// SORT_SMALL_FIRST_BY_OTHER_V( pics, freedom );
// }
F_I_PE(pics, i, p, ith)
int pre_x, pre_y;
pre_x = coord[ith].A;
pre_y = coord[ith].B;
if (coord[ith].A > -1)
remove_from_G( p, coord[ith] );
int best_x, best_y=best_x=0;
VP_II bst = find_best_place_for_pic(p, 1./(1.+ last_iter_bonus + (float)doitagain*doitagain) , 1./(1.+ last_iter_bonus + (float)doitagain*doitagain), pre_x, pre_y);
// int rnd = rand() % SZ(bst);
int rnd = rand() % SZ(bst);
best_x = bst[rnd].A;
best_y = bst[rnd].B;
// coord[ith] = { best_x, best_y };
add_to_G(p, best_x, best_y, coord[ith]);
}
SHUFFLE(pics)
}
out = G_to_VS();
pdd = score_strings(grids, out, coord);
if(pdd.A<best_score || best_score > 10)
{
cerr << rnd_iter << " " +COL_Y_BG + STR( pdd.A ) +" error | compression "+ STR( pdd.B ) + " | sum " + STR( pdd.A+pdd.B ) + COL_END << " " << SZ(pics) <<" size, cleared "<< SZ(pics) / exp << " ";
cerr << " "+COL_B << TIME_SINCE(iter_start_time) << COL_END << END;
UNCONDITIONAL_UPDATE (
best_score
, pdd.A
, best_out
, out
, best_coord
, coord
)
if(pdd.A<0.0001)
break;
past_G = G;
past_G_coord = coord;
}
else
if(RND_CHANCE < 0.9)
{
G = past_G;
coord = past_G_coord;
}
int clear_this_many = (int)floor(SZ(pics) / exp);
// clear_this_many = min( 10 ,clear_this_many);
clear_this_many = max(5,clear_this_many);
if(clear_this_many > 6 || ( N_rects<20 && clear_this_many > 3))
{
// SHUFFLE(pics)
F_I_PE(pics, i, p, ith)
if (
i
> clear_this_many
)
break;
if (coord[ith].A == -1)
continue;
remove_from_G( p, coord[ith] );
}
}
else
{
F(clear_this_many, c)
int i = rand() % SZ(pics);
int ith = pics[i].B;
if (coord[ith].A == -1)
continue;
remove_from_G( pics[i].A, coord[ith] );
}
}
// break;
rnd_iter++;
if (
TIME_SINCE(iter_start_time)
> time_given
// MAX_TIME_ON_RND_TRY
)
break;
}
overall_iterations += rnd_iter;
// CERR("HERE STILL WORKS")
out = best_out;
coord = best_coord;
pdd = score_strings(grids, out, coord);
cerr << COL_Y_BG + STR( pdd.A ) +" error | compression "+ STR( pdd.B ) + COL_END << " SCORE " << COL_G + STR( pdd.A+pdd.B ) << " "+COL_Y + STR( pdd.A /(1.-P) ) +" loss | compr 1 <- "+ STR( 1./(pdd.B/P) ) + COL_END;
cerr << " "+COL_B << TIME_SINCE(iter_start_time) << " iterations: " << rnd_iter << COL_END << END;
if(SZ(stats_file_name) > 2)
{
CERR(stats_file_name)
ofstream outf;
outf.open(stats_file_name, fstream::out | fstream::app);
outf<< SZ(grids) << " " << T_total_px <<" "<< SZ(out) * SZ(out[0]) << " " << pdd.A /(1.-P) << END;
outf.flush();
outf.close();
}
// F_I_PE(coord, i , x, y)
// CERR(x,y)
// }
// CERR("WHAT AB")
previously_calculated[pW][pH] = {past_G, past_G_coord}; // Store best case G and coord for later processing continuation.
propagate_max_expected_error(pW,pH, pdd.A, TIME_SINCE(iter_start_time));
// CERR("WHAT AB?AS")
return { {out , coord}, pdd };
}
int gen_and_upd_if_better(float time_given, int dW, int dH, int ultimate=0, int force=0)
{
int result_H = maxHeight +dH;
int result_W = maxWidth +dW;
float area = result_H*result_W;
return_type nu = findSolution(time_given, dW,dH, best_sol.B.A + best_sol.B.B, ultimate, force);
cerr << COL_B << TIME_SINCE(time_start) << COL_END << " " << result_W << "x" << result_H << END << END;
// cerr << "OPTIONAL [Testing with wall & zero_start]" << END;
// return_type nu_2 = findSolution(dW,dH, ret.B.A+ret.B.B, ultimate, force, (float)T_total_px/area < 2. , (float)T_total_px/area > 3.);
// return_type nu_2 = findSolution(dW,dH, ret.B.A+ret.B.B, ultimate, force);
// // return_type nu_2 = findSolution(dW,dH, ret.B.A+ret.B.B, ultimate, force);
// cerr << COL_B << TIME_SINCE(time_start) << COL_END << " " << result_W << "x" << result_H << END << END;
// if (
// nu_2.B.A + nu_2.B.B
// < nu.B.A + nu.B.B
// )
// nu = nu_2;
// cerr << "Testing zero-start" << END;
// nu_2 = findSolution(dW,dH, ret.B.A+ret.B.B, ultimate, force, 0, 1);
// // nu_2 = findSolution(dW,dH, ret.B.A+ret.B.B, ultimate, force);
// cerr << COL_B << TIME_SINCE(time_start) << COL_END << " " << maxWidth+dW << "x" << maxHeight+dH << END << END;
// if (
// nu_2.B.A + nu_2.B.B
// < nu.B.A + nu.B.B
// )
// nu = nu_2;
// CERR("asd")
if (
best_sol.B.A + best_sol.B.B
> nu.B.A + nu.B.B
)
{
// CERR("fosdipoiOI")
best_sol=nu;
// CERR("djskdajsdlkj")
return 1;
}
// CERR("9832r830")
return 0;
}
int main(int argc, char* argv[])
{
pregenerate_SQRT();
if (argc == 4)
{
stats_file_name = argv[3];
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
srand ( unsigned ( time(0) ) );
SET_COUT_PRECISION(5)
SET_COUT_FIX_PRECISION
TIME(time_start);
cin >> P;
cerr<<P<<END;
int N;
cin >> N;
cerr<<N<<END;
N_rects = N;
for (int i=0;i<N;i++)
{
int H;
cin >> H;
// cerr<<H<<END;
vector<string> grid(H);
for (int y=0;y<H;y++)
{
cin >> grid[y];
// cerr<< grid[y] <<END;
T_total_px += SZ(grid[y]);
}
grids.push_back(grid);
}
rev_p = (1.-P) / ( (float)T_total_px * 12.5 );
p_tot_px= P/(float)T_total_px;
val_per_tile = P*13.5;
F_I_E(grids, i, g)
MAXIMIZE( maxHeight , SZ(g) )
MAXIMIZE( maxWidth , SZ(g[0]) )
MINIMIZE( minHeight , SZ(g) )
MINIMIZE( minWidth , SZ(g[0]) )
VVI pic = VS_to_numbers(g);
pics.PUSH( {pic, i} );
}
// vi_stat_key = find_for(P, N, stat_keys);
// vi_stat_val = find_for(P, N, stat_vals);
// int stat_i = LOW_BOUND_I(vi_stat_key, T_total_px);
// if (SZ(vi_stat_key) <= stat_i)
// stat_i--;
// if (vi_stat_key[stat_i] > T_total_px && stat_i>0)
// stat_i--;
// stat_at_least_this_many_outs = vi_stat_val[ stat_i ];
// stat_a_bit_more_outs = max( stat_at_least_this_many_outs+10, (int)floor(stat_at_least_this_many_outs * 1.05));
// if (stat_i+1 < SZ(vi_stat_key))
// stat_a_bit_more_outs = vi_stat_val[ stat_i+1 ];
// MAXIMIZE(stat_at_least_this_many_outs, maxHeight * maxWidth)
// MAXIMIZE(stat_a_bit_more_outs, maxHeight * maxWidth)
// CERR(COL_B + "Output area is extremely unlikely to be less than", stat_at_least_this_many_outs, COL_B + ", might be even larger than", stat_a_bit_more_outs, COL_B + "squares")
float time_granule = 0.04;
float larger_time_granule = 0.1;
best_sol = findSolution(time_granule, 0, 0, 0, 1);
F(80,y)
F(80,x)
int w = maxWidth +x;
int h = maxHeight+y;
if (
// abs(x-y)<20
// &&
(
x>15
&&
y>15
&&
( (float)max(x,y) / (float)min(x,y) < 2 )
&&
(
T_total_px * 1.2 < w*h
)
)
||
(
T_total_px
> 300
&&
x>20
&&
y>20
&&
( (float)max(x,y) / (float)min(x,y) < 1.5 )
&&
(
T_total_px * 1.05 < w*h
)
)
||
(
T_total_px
> 500
&&
x>30
&&
y>30
&&
( (float)max(x,y) / (float)min(x,y) < 5 )
&&
(
T_total_px * 2 < w*h
)
)
)
{
propagate_max_expected_error(x, y, 0, 0.);
}
}}
F(60, y)
F(90, x)
int SX = maxWidth + x;
int SY = maxHeight + y;
if (
(
T_total_px < 45*15
||
(
P <= 0.1
&& (
(
SX*SY < T_total_px*1.1
&& SX*SY > T_total_px*0.95
)
|| (
SX*SY < 500
&& SX*SY > T_total_px*0.65
&& SX*SY < T_total_px*1.3
)
)
)
||
(
P >= 0.1
&& P <= 0.15
&& (
(
SX*SY < T_total_px*1.05
&& SX*SY > T_total_px*0.8
)
|| (
SX*SY < 500
&& SX*SY > T_total_px*0.65
&& SX*SY < T_total_px*1.2
)
)
)
||
(
P >= 0.15
&& P <= 0.22
&& SX*SY < T_total_px*1.05
&& SX*SY > T_total_px*0.7
)
||
(
P >= 0.22
&& P <= 0.3
&& SX*SY < T_total_px*0.9
&& SX*SY > T_total_px*0.1
// && SX*SY < 2000
)
||
(
P >= 0.3
&& P <= 0.4
&&
(
(
T_total_px >= 45*80
&& SX*SY < T_total_px*0.65
)
||
(
T_total_px <= 45*80
&& T_total_px >= 45*50
&& SX*SY < T_total_px*0.8
)
||
(
T_total_px <= 45*40
&& T_total_px >= 45*15
&& SX*SY < T_total_px*0.9
)
|| SX*SY < 250
)
&& SX*SY < 2500
)
||
(
P >= 0.4
&& P <= 0.45
&&
(
(
T_total_px >= 45*80
&& SX*SY < T_total_px*0.25
)
||
(
T_total_px <= 45*80
&& T_total_px >= 45*40
&& SX*SY < T_total_px*0.3
)
||
(
T_total_px <= 45*40
&& SX*SY < T_total_px*0.4
)
|| SX*SY < 250
)
&& SX*SY < 600
)
||
(
P >= 0.45
&& P <= 0.55
&&
(
(
T_total_px >= 45*80
&& SX*SY < T_total_px*0.15
)
||
(
T_total_px <= 45*80
&& T_total_px >= 45*40
&& SX*SY < T_total_px*0.22
)
||
(
T_total_px <= 45*40
&& SX*SY < T_total_px*0.3
)
|| SX*SY < 250
)
&& SX*SY > T_total_px*0.15
&& SX*SY < 2500
)
||
(
P >= 0.55
&& P <= 0.6
&&
(
(
T_total_px >= 45*80
&& SX*SY < T_total_px*0.15
)
||
(
T_total_px <= 45*80
&& T_total_px >= 45*40
&& SX*SY < T_total_px*0.25
)
||
(
T_total_px <= 45*40
&& SX*SY < T_total_px*0.3
)
|| SX*SY < 200
)
&& SX*SY > T_total_px*0.15
&& SX*SY < 400
)
)
&&
(
SX*SY < T_total_px*1.1
|| (
SX*SY < T_total_px*1.2
&& SX*SY < 900
)
)
&& abs(x-y)<30
&& !res_makes_no_sense(SX,SY)
)
{
// CERR("..")
if (
abs(x-y)<12
|| SX*SY < 500
||
(
abs(x-y)<15
|| SX*SY < 700
)
)
if (
x%3==0 && y%3==0
||
(
x%2==0 && y%2==0
&& T_total_px < 1000
&& P < 0.35
)
||
(
T_total_px < 800
&& P < 0.35
)
||
(
T_total_px < 1300
&& P < 0.22
)
)
if (
T_total_px < 45*15
||
P < 0.55
||
(
SX*SY < 800
)
)
{
// CERR("--")
if (
TIME_SINCE(time_start) < 4
||
(
P< 0.4
&& TIME_SINCE(time_start) < 7.5
)
)
if ( T_total_px < 500
&& P<0.3
)
gen_and_upd_if_better(time_granule, x,y);
else
gen_and_upd_if_better(time_granule, x,y);
}
}
}
}
float time_on_top_search = TIME_SINCE(time_start);
P_II res_chosen;
VP_II all_tested;
if (
P > 0.45
)
F(5, y)
F(6, x)
gen_and_upd_if_better(larger_time_granule, x,y);
}}
// else
// CERR("DOING DA WHILE SEARCH")
while(1)
{
res_chosen = get_res_with_top_potential();
all_tested.PUSH(res_chosen);
if(res_chosen.A<0 || TIME_SINCE(time_start)>3.)
break;
gen_and_upd_if_better(time_granule, res_chosen.A, res_chosen.B);
}
float time_when_started_final_cut = TIME_SINCE(time_start);
int best_dX = SZ(best_sol.A.A[0]) -maxWidth;
int best_dy = SZ(best_sol.A.A) -maxHeight;
CERR(COL_G_BG+"And now, exploiting the final one")
gen_and_upd_if_better( 9.5-TIME_SINCE(time_start) , best_dX, best_dy);
CERR(COL_G_BG+"time_on_top_search", time_on_top_search)
CERR(COL_G_BG+"time_when_started_final_cut", time_when_started_final_cut)
CERR(COL_G_BG+"All tested resolutions")
out_line_VP(all_tested, cerr);
// out_line_VP(previously_calculated_resolutions, cerr);
char mtrx[128][128]={};
F(120, y)
F(120, x)
mtrx[y][x] = '-';
}
}
F_I_PE(previously_calculated_resolutions, i, x,y)
mtrx[y][x] = '+';
}
F_I_PE(all_tested, i, x,y)
mtrx[y][x] = 'O';
}
F(60, y)
string checked="";
F(90, x)
checked += mtrx[y][x];
}
CERR(checked)
}
return_type ret = best_sol;
cerr << COL_G + "SELECTED " + STR( ret.B.A + ret.B.B ) + " <- " + COL_Y_BG + STR( ret.B.A ) +" error | compression "+ STR( ret.B.B ) + COL_END << END;
while( ret.A.A.back() == string( SZ(ret.A.A[0]) ,'-') )
{
ret.A.A.pop_back();
CERR(COL_G+"popped!")
}
F_I_E(ret.A.A, i,e)
F_E(e, s)
if(s=='-')
s='M';
}}
cout << SZ(ret.A.A) << endl;
cerr << COL_R_BG << SZ(ret.A.A[0]) << " X " << SZ(ret.A.A) << COL_END << endl;
F_E(ret.A.A, line)
cerr << line << endl;
COUT(line);
}
if (argc > 2)
{
ofstream outf;
string file_path_and_name = argv[1];
string seed = argv[2];
outf.open(file_path_and_name, fstream::out | fstream::app);
outf<< seed << " " << ret.B.A + ret.B.B << END;
outf.flush();
outf.close();
cerr << seed << COL_R_BG<<" Should be flushed into file" <<COL_END<< END;
}
cerr << COL_B << TIME_SINCE(time_start) << " iterations: " << overall_iterations << COL_END << END;
F_I_PE(ret.A.B, i, x,y)
COUT(y,x);
}
cout.flush();
CERR(qwe);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment