Last active
March 28, 2020 11:38
-
-
Save ibmua/ae06986903be5a133bbfbb49befbb045 to your computer and use it in GitHub Desktop.
TopCoder Marathon Match 116 solution
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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