197afdc1d0 2015-03-26 kinaba: #include <iostream> 197afdc1d0 2015-03-26 kinaba: #include <sstream> 197afdc1d0 2015-03-26 kinaba: #include <iomanip> 197afdc1d0 2015-03-26 kinaba: #include <vector> 197afdc1d0 2015-03-26 kinaba: #include <string> 197afdc1d0 2015-03-26 kinaba: #include <map> 197afdc1d0 2015-03-26 kinaba: #include <set> 197afdc1d0 2015-03-26 kinaba: #include <algorithm> 197afdc1d0 2015-03-26 kinaba: #include <numeric> 197afdc1d0 2015-03-26 kinaba: #include <iterator> 197afdc1d0 2015-03-26 kinaba: #include <functional> 197afdc1d0 2015-03-26 kinaba: #include <complex> 197afdc1d0 2015-03-26 kinaba: #include <queue> 197afdc1d0 2015-03-26 kinaba: #include <stack> 197afdc1d0 2015-03-26 kinaba: #include <cmath> 197afdc1d0 2015-03-26 kinaba: #include <cassert> 197afdc1d0 2015-03-26 kinaba: #include <tuple> 197afdc1d0 2015-03-26 kinaba: using namespace std; 197afdc1d0 2015-03-26 kinaba: typedef long long LL; 197afdc1d0 2015-03-26 kinaba: typedef complex<double> CMP; 197afdc1d0 2015-03-26 kinaba: 197afdc1d0 2015-03-26 kinaba: template<typename T> 197afdc1d0 2015-03-26 kinaba: class IdGen 197afdc1d0 2015-03-26 kinaba: { 197afdc1d0 2015-03-26 kinaba: map<T, int> v2id_; 197afdc1d0 2015-03-26 kinaba: vector<T> id2v_; 197afdc1d0 2015-03-26 kinaba: public: 197afdc1d0 2015-03-26 kinaba: int v2id(const T& v) { 197afdc1d0 2015-03-26 kinaba: if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } 197afdc1d0 2015-03-26 kinaba: return v2id_[v]; 197afdc1d0 2015-03-26 kinaba: } 197afdc1d0 2015-03-26 kinaba: const T& id2v(int i) const { return id2v_[i]; } 197afdc1d0 2015-03-26 kinaba: int size() const { return id2v_.size(); } 197afdc1d0 2015-03-26 kinaba: }; 197afdc1d0 2015-03-26 kinaba: 197afdc1d0 2015-03-26 kinaba: template<typename Vert=pair<int,int>, typename Flow=LL, int NV=2048> 197afdc1d0 2015-03-26 kinaba: class MaxFlow 197afdc1d0 2015-03-26 kinaba: { 197afdc1d0 2015-03-26 kinaba: IdGen<Vert> idgen; 197afdc1d0 2015-03-26 kinaba: vector<int> G[NV]; 197afdc1d0 2015-03-26 kinaba: Flow F[NV][NV]; 197afdc1d0 2015-03-26 kinaba: 197afdc1d0 2015-03-26 kinaba: public: 197afdc1d0 2015-03-26 kinaba: void addEdge( Vert s_, Vert t_, Flow f ) 197afdc1d0 2015-03-26 kinaba: { 197afdc1d0 2015-03-26 kinaba: const int s = idgen.v2id(s_), t = idgen.v2id(t_); 197afdc1d0 2015-03-26 kinaba: G[s].push_back(t); 197afdc1d0 2015-03-26 kinaba: G[t].push_back(s); 197afdc1d0 2015-03-26 kinaba: F[s][t] = f; 197afdc1d0 2015-03-26 kinaba: F[t][s] = 0; 197afdc1d0 2015-03-26 kinaba: } 197afdc1d0 2015-03-26 kinaba: 197afdc1d0 2015-03-26 kinaba: Flow calc( Vert s_, Vert t_ ) 197afdc1d0 2015-03-26 kinaba: { 197afdc1d0 2015-03-26 kinaba: const int S = idgen.v2id(s_), D = idgen.v2id(t_); 197afdc1d0 2015-03-26 kinaba: for( Flow total=0 ;; ) { 197afdc1d0 2015-03-26 kinaba: // Do BFS and compute the level for each node. 197afdc1d0 2015-03-26 kinaba: int LV[NV] = {0}; 197afdc1d0 2015-03-26 kinaba: vector<int> Q(1, S); 197afdc1d0 2015-03-26 kinaba: for(int lv=1; !Q.empty(); ++lv) { 197afdc1d0 2015-03-26 kinaba: vector<int> Q2; 197afdc1d0 2015-03-26 kinaba: for(size_t i=0; i!=Q.size(); ++i) { 197afdc1d0 2015-03-26 kinaba: const vector<int>& ne = G[Q[i]]; 197afdc1d0 2015-03-26 kinaba: for(size_t j=0; j!=ne.size(); ++j) 197afdc1d0 2015-03-26 kinaba: if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S ) 197afdc1d0 2015-03-26 kinaba: LV[ne[j]]=lv, Q2.push_back(ne[j]); 197afdc1d0 2015-03-26 kinaba: } 197afdc1d0 2015-03-26 kinaba: Q.swap(Q2); 197afdc1d0 2015-03-26 kinaba: } 197afdc1d0 2015-03-26 kinaba: 197afdc1d0 2015-03-26 kinaba: // Destination is now unreachable. Done. 197afdc1d0 2015-03-26 kinaba: if( !LV[D] ) 197afdc1d0 2015-03-26 kinaba: return total; 197afdc1d0 2015-03-26 kinaba: 197afdc1d0 2015-03-26 kinaba: // Iterating DFS. 197afdc1d0 2015-03-26 kinaba: bool blocked[NV] = {}; 197afdc1d0 2015-03-26 kinaba: total += dinic_dfs( S, D, LV, 0x7fffffff, blocked ); 197afdc1d0 2015-03-26 kinaba: } 197afdc1d0 2015-03-26 kinaba: } 197afdc1d0 2015-03-26 kinaba: 197afdc1d0 2015-03-26 kinaba: private: 197afdc1d0 2015-03-26 kinaba: Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] ) 197afdc1d0 2015-03-26 kinaba: { 197afdc1d0 2015-03-26 kinaba: Flow flow_out = 0; 197afdc1d0 2015-03-26 kinaba: for(size_t i=0; i!=G[v].size(); ++i) { 197afdc1d0 2015-03-26 kinaba: int u = G[v][i]; 197afdc1d0 2015-03-26 kinaba: if( LV[v]+1==LV[u] && F[v][u] ) { 197afdc1d0 2015-03-26 kinaba: Flow f = min(flow_in-flow_out, F[v][u]); 197afdc1d0 2015-03-26 kinaba: if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f,blocked))>0 ) { 197afdc1d0 2015-03-26 kinaba: F[v][u] -= f; 197afdc1d0 2015-03-26 kinaba: F[u][v] += f; 197afdc1d0 2015-03-26 kinaba: flow_out += f; 197afdc1d0 2015-03-26 kinaba: if( flow_in == flow_out ) return flow_out; 197afdc1d0 2015-03-26 kinaba: } 197afdc1d0 2015-03-26 kinaba: } 197afdc1d0 2015-03-26 kinaba: } 197afdc1d0 2015-03-26 kinaba: blocked[v] = (flow_out==0); 197afdc1d0 2015-03-26 kinaba: return flow_out; 197afdc1d0 2015-03-26 kinaba: } 197afdc1d0 2015-03-26 kinaba: }; 197afdc1d0 2015-03-26 kinaba: 197afdc1d0 2015-03-26 kinaba: class Singing { public: 197afdc1d0 2015-03-26 kinaba: int solve(int N, int low, int high, vector <int> pitch) 197afdc1d0 2015-03-26 kinaba: { 197afdc1d0 2015-03-26 kinaba: map<pair<int,int>, int> edge; 197afdc1d0 2015-03-26 kinaba: for(int i=0; i+1<pitch.size(); ++i) { 197afdc1d0 2015-03-26 kinaba: int p0 = min(pitch[i], pitch[i+1]); 197afdc1d0 2015-03-26 kinaba: int p1 = max(pitch[i], pitch[i+1]); 197afdc1d0 2015-03-26 kinaba: if(p0 != p1) 197afdc1d0 2015-03-26 kinaba: edge[make_pair(p0,p1)] ++; 197afdc1d0 2015-03-26 kinaba: } 197afdc1d0 2015-03-26 kinaba: 197afdc1d0 2015-03-26 kinaba: MaxFlow<>* mf = new MaxFlow<>; 197afdc1d0 2015-03-26 kinaba: const LL INF = 0x3fffffff; 197afdc1d0 2015-03-26 kinaba: 197afdc1d0 2015-03-26 kinaba: enum{BOB, LEFT, RIGHT, ALICE}; 197afdc1d0 2015-03-26 kinaba: pair<int,int> Bob(BOB,0); 197afdc1d0 2015-03-26 kinaba: pair<int,int> Alice(ALICE,0); 197afdc1d0 2015-03-26 kinaba: for(int v=1; v<=N; ++v) { 197afdc1d0 2015-03-26 kinaba: if(v>high) 197afdc1d0 2015-03-26 kinaba: mf->addEdge(Bob, make_pair(LEFT,v), INF); 197afdc1d0 2015-03-26 kinaba: mf->addEdge(make_pair(LEFT,v), make_pair(RIGHT,v), INF); 197afdc1d0 2015-03-26 kinaba: if(v<low) 197afdc1d0 2015-03-26 kinaba: mf->addEdge(make_pair(RIGHT,v), Alice, INF); 197afdc1d0 2015-03-26 kinaba: } 197afdc1d0 2015-03-26 kinaba: for(auto e: edge) { 197afdc1d0 2015-03-26 kinaba: int v = e.first.first; 197afdc1d0 2015-03-26 kinaba: int u = e.first.second; 197afdc1d0 2015-03-26 kinaba: int c = e.second; 197afdc1d0 2015-03-26 kinaba: mf->addEdge(make_pair(RIGHT,v), make_pair(LEFT,u), c); 197afdc1d0 2015-03-26 kinaba: mf->addEdge(make_pair(RIGHT,u), make_pair(LEFT,v), c); 197afdc1d0 2015-03-26 kinaba: } 197afdc1d0 2015-03-26 kinaba: 197afdc1d0 2015-03-26 kinaba: LL ans = mf->calc(Bob, Alice); 197afdc1d0 2015-03-26 kinaba: delete mf; 197afdc1d0 2015-03-26 kinaba: return int(ans); 197afdc1d0 2015-03-26 kinaba: } 197afdc1d0 2015-03-26 kinaba: }; 197afdc1d0 2015-03-26 kinaba: 197afdc1d0 2015-03-26 kinaba: // BEGIN CUT HERE 197afdc1d0 2015-03-26 kinaba: #include <ctime> 197afdc1d0 2015-03-26 kinaba: double start_time; string timer() 197afdc1d0 2015-03-26 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 197afdc1d0 2015-03-26 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 197afdc1d0 2015-03-26 kinaba: { os << "{ "; 197afdc1d0 2015-03-26 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 197afdc1d0 2015-03-26 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 197afdc1d0 2015-03-26 kinaba: void verify_case(const int& Expected, const int& Received) { 197afdc1d0 2015-03-26 kinaba: bool ok = (Expected == Received); 197afdc1d0 2015-03-26 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 197afdc1d0 2015-03-26 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 197afdc1d0 2015-03-26 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 197afdc1d0 2015-03-26 kinaba: #define END verify_case(_, Singing().solve(N, low, high, pitch));} 197afdc1d0 2015-03-26 kinaba: int main(){ 197afdc1d0 2015-03-26 kinaba: 197afdc1d0 2015-03-26 kinaba: CASE(0) 197afdc1d0 2015-03-26 kinaba: int N = 3; 197afdc1d0 2015-03-26 kinaba: int low = 2; 197afdc1d0 2015-03-26 kinaba: int high = 2; 197afdc1d0 2015-03-26 kinaba: int pitch_[] = {1,2,3,2,1,2}; 197afdc1d0 2015-03-26 kinaba: vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_)); 197afdc1d0 2015-03-26 kinaba: int _ = 2; 197afdc1d0 2015-03-26 kinaba: END 197afdc1d0 2015-03-26 kinaba: CASE(1) 197afdc1d0 2015-03-26 kinaba: int N = 10; 197afdc1d0 2015-03-26 kinaba: int low = 3; 197afdc1d0 2015-03-26 kinaba: int high = 7; 197afdc1d0 2015-03-26 kinaba: int pitch_[] = {4,4,5,5,6,5,3,6}; 197afdc1d0 2015-03-26 kinaba: vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_)); 197afdc1d0 2015-03-26 kinaba: int _ = 0; 197afdc1d0 2015-03-26 kinaba: END 197afdc1d0 2015-03-26 kinaba: CASE(2) 197afdc1d0 2015-03-26 kinaba: int N = 6; 197afdc1d0 2015-03-26 kinaba: int low = 2; 197afdc1d0 2015-03-26 kinaba: int high = 5; 197afdc1d0 2015-03-26 kinaba: int pitch_[] = {5,3,1,6,4,2}; 197afdc1d0 2015-03-26 kinaba: vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_)); 197afdc1d0 2015-03-26 kinaba: int _ = 1; 197afdc1d0 2015-03-26 kinaba: END 197afdc1d0 2015-03-26 kinaba: CASE(3) 197afdc1d0 2015-03-26 kinaba: int N = 10; 197afdc1d0 2015-03-26 kinaba: int low = 4; 197afdc1d0 2015-03-26 kinaba: int high = 5; 197afdc1d0 2015-03-26 kinaba: int pitch_[] = {1,4,3,5,2,5,7,5,9}; 197afdc1d0 2015-03-26 kinaba: vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_)); 197afdc1d0 2015-03-26 kinaba: int _ = 3; 197afdc1d0 2015-03-26 kinaba: END 197afdc1d0 2015-03-26 kinaba: CASE(4) 197afdc1d0 2015-03-26 kinaba: int N = 100; 197afdc1d0 2015-03-26 kinaba: int low = 20; 197afdc1d0 2015-03-26 kinaba: int high = 80; 197afdc1d0 2015-03-26 kinaba: int pitch_[] = {2,27,3,53,53,52,52,60,85,89,100,53,60,2,3,53,100,89,40,42,2,53,2,85}; 197afdc1d0 2015-03-26 kinaba: vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_)); 197afdc1d0 2015-03-26 kinaba: int _ = 5; 197afdc1d0 2015-03-26 kinaba: END 197afdc1d0 2015-03-26 kinaba: /* 197afdc1d0 2015-03-26 kinaba: CASE(5) 197afdc1d0 2015-03-26 kinaba: int N = ; 197afdc1d0 2015-03-26 kinaba: int low = ; 197afdc1d0 2015-03-26 kinaba: int high = ; 197afdc1d0 2015-03-26 kinaba: int pitch_[] = ; 197afdc1d0 2015-03-26 kinaba: vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_)); 197afdc1d0 2015-03-26 kinaba: int _ = ; 197afdc1d0 2015-03-26 kinaba: END 197afdc1d0 2015-03-26 kinaba: CASE(6) 197afdc1d0 2015-03-26 kinaba: int N = ; 197afdc1d0 2015-03-26 kinaba: int low = ; 197afdc1d0 2015-03-26 kinaba: int high = ; 197afdc1d0 2015-03-26 kinaba: int pitch_[] = ; 197afdc1d0 2015-03-26 kinaba: vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_)); 197afdc1d0 2015-03-26 kinaba: int _ = ; 197afdc1d0 2015-03-26 kinaba: END 197afdc1d0 2015-03-26 kinaba: */ 197afdc1d0 2015-03-26 kinaba: } 197afdc1d0 2015-03-26 kinaba: // END CUT HERE