Skip to content

Instantly share code, notes, and snippets.

@ibmua

ibmua/sol.cpp

Created March 10, 2020 17:52
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/07f194a59e51c66ff9247a5b28d5aa4b to your computer and use it in GitHub Desktop.
Save ibmua/07f194a59e51c66ff9247a5b28d5aa4b to your computer and use it in GitHub Desktop.
Download ZIP
Code Jam "Costume Change" problem solution
Raw
sol.cpp
/*
// By Ihor Menshykov, MIT license
g++ sol.cpp -fsanitize=address -include bits/stdc++.h -O3 -pthread -lm -std=c++14 -o executables/executable && ulimit -Sv 1000000000000 && time ./executables/executable < ./ins/a
time g++ sol.cpp -O3 -pthread -lm -std=c++14 -o executables/executable && ./executables/executable < ./ins/a
time taskset --cpu-list 0 g++ sol.cpp -include bits/stdc++.h -O3 -pthread -lm -std=c++14 -o executables/executable && ulimit -Sv 1000000 &&
time ./executables/executable < ./ins/a
g++ sol.cpp -Ofast -std=c++17 -I/usr/include/python2.7 -lpython2.7 -lboost_system -lboost_filesystem -o executables/executable &&
./executables/executable < ./ins/a
*/
#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wunused-result"
#pragma GCC diagnostic ignored "-Wregister"
// #pragma GCC optimize ("Ofast")
#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 "defines.cpp"
// namespace plt = matplotlibcpp;
using namespace std;
#define PRIME 919393
#define BILL (LL)1000000000
#define BILLION (LL)1000000000
#define QUAN (LL)1000000000000000000
#define QUANTILLION (LL)1000000000000000000
#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 SHUFFLE(r) shuffle( ALL(r) , mt_rnd);
#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 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 FROM_PII(p, x,y) int x=p.A; int y=p.B;
#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 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_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_PII_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_XX(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_UNIQ(v) v.erase( UNIQ(v) , v.end() );
#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 MINIMIZE(a,b) a=min((a),(b));
#define MAXIMIZE(a,b) a=max((a),(b));
#define UNCONDITIONAL_UPDATE(nu, nu_id, best, best_id) { best = nu; best_id = nu_id; }
#define UNCONDITIONAL_UPDATE_2(nu, nu_id, nu_2, best, best_id, best_2) { best = nu; best_id = nu_id; best_2 = nu_2; }
#define UNCONDITIONAL_UPDATE_3(nu, nu_id, nu_2, nu_3, best, best_id, best_2, best_3) { best = nu; best_id = nu_id; best_2 = nu_2; best_3 = nu_3; }
#define IF_LESS_UPDATE(nu, nu_id, best, best_id) if(nu < best) { best = nu; best_id = nu_id; }
#define IF_MORE_UPDATE(nu, nu_id, best, best_id) if(nu > best) { best = nu; best_id = nu_id; }
#define IF_LESS_UPDATE_2(nu, nu_id, nu_2, best, best_id, best_2) if(nu < best) { best = nu; best_id = nu_id; best_2 = nu_2; }
#define IF_LESS_UPDATE_3(nu, nu_id, nu_2, nu_3, best, best_id, best_2, best_3) if(nu < best) { best = nu; best_id = nu_id; best_2 = nu_2; best_3 = nu_3; }
#define IF_MORE_UPDATE_2(nu, nu_id, nu_2, best, best_id, best_2) if(nu > best) { best = nu; best_id = nu_id; best_2 = nu_2; }
#define IF_MORE_UPDATE_3(nu, nu_id, nu_2, nu_3, best, best_id, best_2, best_3) if(nu > best) { best = nu; best_id = nu_id; best_2 = nu_2; best_3 = nu_3; }
#define IF_LESS_EQ_UPDATE(nu, nu_id, best, best_id) if( nu < best || (nu == best) ) { best = nu; best_id = nu_id; }
#define IF_MORE_EQ_UPDATE(nu, nu_id, best, best_id) if( nu > best || (nu == best) ) { best = nu; best_id = nu_id; }
#define IF_LESS_EQ_UPDATE_2(nu, nu_id, nu_2, best, best_id, best_2) if( nu < best || (nu == best) ) { best = nu; best_id = nu_id; best_2 = nu_2; }
#define IF_MORE_EQ_UPDATE_2(nu, nu_id, nu_2, best, best_id, best_2) if( nu > best || (nu == best) ) { best = nu; best_id = nu_id; best_2 = nu_2; }
#define IF_LESS_EQ_RND_UPDATE(nu, nu_id, best, best_id) if( nu < best || ((nu == best) && (rand()%2)) ) { best = nu; best_id = nu_id; }
#define IF_MORE_EQ_RND_UPDATE(nu, nu_id, best, best_id) if( nu > best || ((nu == best) && (rand()%2)) ) { best = nu; best_id = nu_id; }
#define IF_LESS_EQ_RND_UPDATE_2(nu, nu_id, nu_2, best, best_id, best_2) if( nu < best || ((nu == best) && (rand()%2)) ) { best = nu; best_id = nu_id; best_2 = nu_2; }
#define IF_MORE_EQ_RND_UPDATE_2(nu, nu_id, nu_2, best, best_id, best_2) if( nu > best || ((nu == best) && (rand()%2)) ) { best = nu; best_id = nu_id; best_2 = nu_2; }
#define IF_THEN_UPDATE (cond, nu_id, best_id) if( cond ) { best_id = nu_id; }
#define IF_THEN_UPDATE_2(cond, nu_id, nu_2, best_id, best_2) if( cond ) { best_id = nu_id; best_2 = nu_2; }
#define IF_THEN_UPDATE_3(cond, nu, nu_id, nu_2, best, best_id, best_2) if( cond ) { best = nu; best_id = nu_id; best_2 = nu_2; }
// #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_FROM(n,i,f) for (int i = f; i < (n); ++i) {
#define F_FROM_DOWN_TO(n,t,i) for (int i = (n); i >= (t); --i) {
#define F_I_F_T(i,f,t) for (int i = f; f<t ? i<=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_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_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_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(v,val) FIND(v,val) - v.begin()
#define THIS_EL_INSIDE(k,m) m.find( k ) != m.end()
#define THIS_EL_NOT_INSIDE(k,m) m.find( k ) == m.end()
#define IF_THIS_EL_INSIDE(k,m) if( m.find( k ) != m.end() )
#define IF_THIS_EL_NOT_INSIDE(k,m) if( m.find( k ) == m.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 OUT(...) CONCAT_2(OUT_ , N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define COUT(...) CONCAT_2(COUT_, 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_FAKE_INPUT(s) stringstream fake_iss; 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(g) a.PUSH(g);}
// #define IN_S_PUSH(a) {IN_S(g) a.PUSH(g);}
// #define IN_F_PUSH(a) {IN_F(g) a.PUSH(g);}
// #define IN_P_PUSH(a) {IN_P(g) a.PUSH(g);}
// #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_VAR(...) 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;
}
VI Range( int f, int t ) // int range [F , T)
{
VI rng(t-f);
F_I_F_T(i,f,t)
rng[i] = i;
}
return rng;
}
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<int, int> m;
F_elem(e,v)
{
m[ e ]++;
}
return m;
}
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(vector<T> &v)
{
F_all(i,v)
{
std::cout << v[i] << " ";
}
std::cout << END;
}
template <class T>
void out_line_VV(vector<T> &v)
{
F_all(i,v)
{
out_line_V(v[i]);
}
std::cout << END;
}
template <class T>
void out_line_VP(vector<T> &v)
{
F_all(i,v)
{
std::cout << v[i].A << " " << v[i].B << " | ";
}
std::cout << 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;
// }
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;
}
LD SQRT2 = sqrt(2);
LD SQRT3 = sqrt(3);
LD SQRT5 = sqrt(5);
VI AROUND_4X = {0,0 ,1,-1};
VI AROUND_4Y = {-1,1 ,0,0};
VI AROUND_9X = {0,0 ,1,-1 ,1,-1 ,-1,1};
VI AROUND_9Y = {-1,1 ,0,0 ,1,-1 ,1,-1};
class lossy_bipartite_match // By Ihor Menshykov
{
public:
int n,m;
VVI lk;
VI s;
lossy_bipartite_match( int _n, int _m ) : n(_n), m(_m)
{
assert(0 <= n && 0 <= m);
// COUT(n,m)
lk.resize(n+m);
s.resize(n+m);
}
void add(int f, int t)
{
lk[f ].PUSH(n+t);
lk[n+t].PUSH(f);
}
VP_II match(int quick = 0)
{
VP_II matches;
F_I_E(lk, i, e)
s[i] = SZ(e);
}
while(1)
{
int least = BILLION;
VI best_ones;
F_I_E(s, i , sa)
if(sa < 1)
continue;
if (sa == least && !quick)
{
best_ones.PUSH(i);
}
else
if (sa < least)
{
best_ones.resize(1);
best_ones[0] = i;
least = sa;
}
}
if (SZ(best_ones) == 0)
return matches;
int best_a = -1;
int best_b = -1;
int least_sb = BILLION;
F_E(best_ones, a)
int brk = 0;
F_E(lk[a], b)
if(s[b] < 1)
continue;
if(s[b] == least)
brk = 1;
IF_LESS_UPDATE_2(
s[b]
, b
, a
, least_sb
, best_b
, best_a
)
if(brk)
break;
}
if(brk)
break;
}
F_E( lk[best_a] , e)
s[e]--;
}
F_E( lk[best_b] , e)
s[e]--;
}
s[best_a] = 0;
s[best_b] = 0;
MIN_MAX( best_a , best_b );
matches.emplace_back( best_a, best_b - n );
// COUT( best_a , best_b - n )
}
}
};
class matching { // By Gennady Korotkevich aka Tourist
public:
vector< vector<int> > g;
vector<int> pa;
vector<int> pb;
vector<int> was;
int n, m;
int res;
int iter;
matching(int _n, int _m) : n(_n), m(_m) {
assert(0 <= n && 0 <= m);
pa = vector<int>(n, -1);
pb = vector<int>(m, -1);
was = vector<int>(n, 0);
g.resize(n);
res = 0;
iter = 0;
}
void add(int from, int to) {
assert(0 <= from && from < n && 0 <= to && to < m);
g[from].push_back(to);
}
bool dfs(int v) {
was[v] = iter;
for (int u : g[v]) {
if (pb[u] == -1) {
pa[v] = u;
pb[u] = v;
return true;
}
}
for (int u : g[v]) {
if (was[pb[u]] != iter && dfs(pb[u])) {
pa[v] = u;
pb[u] = v;
return true;
}
}
return false;
}
int solve() {
while (true) {
iter++;
int add = 0;
for (int i = 0; i < n; i++) {
if (pa[i] == -1 && dfs(i)) {
add++;
}
}
if (add == 0) {
break;
}
res += add;
}
return res;
}
int run_one(int v) {
if (pa[v] != -1) {
return 0;
}
iter++;
return (int) dfs(v);
}
};
int main(int argc, char* argv[])
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
srand ( unsigned ( time(0) ) );
TIME(time_start);
SET_COUT_PRECISION(20)
SET_COUT_FIX_PRECISION
#ifdef BZ
cin.clear();
freopen("/home/i/C/jam/libraries/ins/a", "r", stdin);
#endif
int wrong_long = 0;
int wrong_quick = 0;
F(1000000,p)
int n=5,m=5;
lossy_bipartite_match my(n,m);
matching mk(n,m);
float chance = clamp(RND_CHANCE + 0.4 , 0.04, 0.96 );
VVI mtrx(n, VI(m,0));
F(n,i)
F(m,w)
if(RND_CHANCE < chance)
{
my.add(i,w);
mk.add(i,w);
mtrx[i][w] = 1;
}
}}
int mks = mk.solve();
VP_II mys = my.match();
VP_II myq = my.match(1); // quicker, but a little bit more lossy
if (
mks != SZ( myq )
)
wrong_quick++;
if (
mks != SZ( mys )
)
{
OUT(COL_R+"Wrong =(", mks, SZ( mys ))
F_E(mys, e)
if(mtrx[ e.A ][ e.B ] == 1)
mtrx[ e.A ][ e.B ] = 3;
else
mtrx[ e.A ][ e.B ] = -1;
}
out_line_VV(mtrx);
exit(0);
wrong_long++;
}
else
{
COUT(p, wrong_long, wrong_quick,"Correct")
}
}
// Code Jam "Costume Change" problem solution
// https://codingcompetitions.withgoogle.com/codejam/round/0000000000007706/0000000000045875
/*
CIN_I(TST)
F(TST,tt)
CIN_I(n)
vector<bipartite_match> m(2*n+1 , bipartite_match(n,n));
F(n,i)
F(n,w)
CIN_I(a)
a+=n;
// lk[a][w+n].PUSH(i );
// lk[a][i ].PUSH(w+n);
m[a].add(i,w);
}}
int co = 0;
F(2*n+1,i)
co += SZ( m[i].match() );
}
CaseOUT( tt+1 , n*n-co)
// OUT(TIME_SINCE(time_start))
}
*/
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment