• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/589-U/1A.cpp version [15460ab419ea2b8c]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +struct UnionFind
           23  +{
           24  + vector<int> uf, sz;
           25  + int nc;
           26  +
           27  + UnionFind(int N): uf(N), sz(N,1), nc(N)
           28  +  { for(int i=0; i<N; ++i) uf[i] = i; }
           29  + int size()
           30  +  { return nc; }
           31  + int size(int a)
           32  +  { return sz[Find(a)]; }
           33  + int Find(int a)
           34  +  { return uf[a]==a ? a : uf[a]=Find(uf[a]); }
           35  + bool Union(int a, int b)
           36  +  {
           37  +   a = Find(a);
           38  +   b = Find(b);
           39  +   if( a != b )
           40  +   {
           41  +    if( sz[a] >= sz[b] ) swap(a, b);
           42  +    uf[a] = b;
           43  +    sz[b] += sz[a];
           44  +    --nc;
           45  +   }
           46  +   return (a!=b);
           47  +  }
           48  +};
           49  +
           50  +class GooseTattarrattatDiv1 { public:
           51  + int getmin(string S)
           52  + {
           53  +  UnionFind uf(128);
           54  +
           55  +  map<char,int> time_for;
           56  +  for(int i=0; i<S.size(); ++i)
           57  +  {
           58  +   time_for[S[i]]++;
           59  +   uf.Union(S[i], S[S.size()-1-i]);
           60  +  }
           61  +
           62  +  int total = 0;
           63  +
           64  +  set<char> done;
           65  +  for(auto c : S)
           66  +  {
           67  +   if(done.count(c))
           68  +    continue;
           69  +
           70  +   int need = 0;
           71  +   int m = 0;
           72  +   for(auto d : S)
           73  +    if(uf.Find(c) == uf.Find(d)) {
           74  +     if(done.count(d))
           75  +      continue;
           76  +     done.insert(d);
           77  +     need += time_for[d];
           78  +     m = max(m, time_for[d]);
           79  +    }
           80  +   total += (need - m);
           81  +  }
           82  +
           83  +  return total;
           84  + }
           85  +};
           86  +
           87  +// BEGIN CUT HERE
           88  +#include <ctime>
           89  +double start_time; string timer()
           90  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           91  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           92  + { os << "{ ";
           93  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           94  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           95  +void verify_case(const int& Expected, const int& Received) {
           96  + bool ok = (Expected == Received);
           97  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           98  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           99  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          100  +#define END  verify_case(_, GooseTattarrattatDiv1().getmin(S));}
          101  +int main(){
          102  +
          103  +CASE(0)
          104  + string S = "geese";
          105  + int _ = 2;
          106  +END
          107  +CASE(1)
          108  + string S = "tattarrattat";
          109  + int _ = 0;
          110  +END
          111  +CASE(2)
          112  + string S = "xyyzzzxxx";
          113  + int _ = 2;
          114  +END
          115  +CASE(3)
          116  + string S = "xrepayuyubctwtykrauccnquqfuqvccuaakylwlcjuyhyammag";
          117  + int _ = 11;
          118  +END
          119  +CASE(4)
          120  + string S = "abaabb";
          121  + int _ = 3;
          122  +END
          123  +/*
          124  +CASE(5)
          125  + string S = ;
          126  + int _ = ;
          127  +END
          128  +CASE(6)
          129  + string S = ;
          130  + int _ = ;
          131  +END
          132  +*/
          133  +}
          134  +// END CUT HERE

Added SRM/589-U/1B.cpp version [d52e6b2498cc7fe5]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +typedef int           vert;
           23  +typedef vert          edge;
           24  +typedef vector<edge>  edges;
           25  +typedef vector<edges> graph;
           26  +
           27  +bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] )
           28  +{
           29  + for(int i=0; i<G[v].size(); ++i) {
           30  +  vert u = G[v][i];
           31  +  if( visited[u] ) continue;
           32  +  visited[u] = true;
           33  +
           34  +  if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) )
           35  +   { matchTo[v]=u, matchTo[u]=v; return true; }
           36  + }
           37  + return false;
           38  +}
           39  +
           40  +template<int NV>
           41  +int biMatch( graph& G, int L ) // [0,L):left, [L,?):right
           42  +    // only left->right edges are used during computation
           43  +{
           44  + vector<vert> matchTo(G.size(), -1);
           45  + int ans = 0;
           46  + for(vert v=0; v<L; ++v) {
           47  +  bool visited[NV] = {};
           48  +  if( augment(G, v, matchTo, visited) )
           49  +   ++ans;
           50  + }
           51  + return ans;
           52  +}
           53  +
           54  +class GearsDiv1 { public:
           55  + int getmin(string color, vector <string> graph)
           56  + {
           57  +  vector<int> r, g, b;
           58  +  for(int i=0; i<color.size(); ++i)
           59  +   (color[i]=='R' ? r : color[i]=='G' ? g : b).push_back(i);
           60  +
           61  +  int rg = calc(graph, r, g);
           62  +  int gb = calc(graph, g, b);
           63  +  int br = calc(graph, b, r);
           64  +  return min(rg, min(gb, br));
           65  + }
           66  +
           67  + int calc(const vector<string>& G, const vector<int>& A, const vector<int>& B)
           68  + {
           69  +  if(A.empty() || B.empty())
           70  +   return 0;
           71  +
           72  +  graph gr(A.size() + B.size());
           73  +  for(int a=0; a<A.size(); ++a)
           74  +  for(int b=0; b<B.size(); ++b)
           75  +  {
           76  +   if(G[A[a]][B[b]] == 'Y')
           77  +    gr[a].push_back(A.size()+b);
           78  +  }
           79  +  return biMatch<256>(gr, A.size());
           80  + }
           81  +};
           82  +
           83  +// BEGIN CUT HERE
           84  +#include <ctime>
           85  +double start_time; string timer()
           86  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           87  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           88  + { os << "{ ";
           89  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           90  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           91  +void verify_case(const int& Expected, const int& Received) {
           92  + bool ok = (Expected == Received);
           93  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           94  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           95  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           96  +#define END  verify_case(_, GearsDiv1().getmin(color, graph));}
           97  +int main(){
           98  +
           99  +CASE(0)
          100  + string color = "RGB";
          101  + string graph_[] = {"NYY","YNY","YYN"};
          102  +   vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
          103  + int _ = 1;
          104  +END
          105  +CASE(1)
          106  + string color = "RGBR";
          107  + string graph_[] = {"NNNN","NNNN","NNNN","NNNN"};
          108  +   vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
          109  + int _ = 0;
          110  +END
          111  +CASE(2)
          112  + string color = "RGBR";
          113  + string graph_[] = {"NYNN","YNYN","NYNY","NNYN"};
          114  +   vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
          115  + int _ = 1;
          116  +END
          117  +CASE(3)
          118  + string color = "RRRRRGRRBGRRGBBGGGBRRRGBRGRRGG";
          119  + string graph_[] = {"NNNNNYNNNYNNYNNNYNNNNNNNNYNNYY",
          120  + "NNNNNNNNYNNNYNYNNYNNNNYNNYNNYY",
          121  + "NNNNNYNNNNNNNNNNNNYNNNNNNYNNNY",
          122  + "NNNNNNNNNYNNYNNYYYNNNNYNNYNNNN",
          123  + "NNNNNNNNNYNNYNNYYYNNNNYNNNNNNN",
          124  + "YNYNNNYYYNNYNYYNNNNNYYNYNNYYNN",
          125  + "NNNNNYNNNNNNNNNYYYNNNNYNNYNNYY",
          126  + "NNNNNYNNNNNNNNNYNNNNNNNNNNNNYN",
          127  + "NYNNNYNNNYNNYNNYYYNNNNYNNYNNYY",
          128  + "YNNYYNNNYNNNNYYNNNYNYYNYNNNNNN",
          129  + "NNNNNNNNNNNNYNNYNYNNNNYNNNNNNY",
          130  + "NNNNNYNNNNNNYNNYYYNNNNNNNNNNYN",
          131  + "YYNYYNNNYNYYNYYNNNYNYNNYNNNNNN",
          132  + "NNNNNYNNNYNNYNNYYYNNNNYNNYNYYY",
          133  + "NYNNNYNNNYNNYNNYYYNNNNYNNYNNYY",
          134  + "NNNYYNYYYNYYNYYNNNYNYNNYYNYYNN",
          135  + "YNNYYNYNYNNYNYYNNNYNNNNYYNNYNN",
          136  + "NYNYYNYNYNYYNYYNNNNYYNNYYNYNNN",
          137  + "NNYNNNNNNYNNYNNYYNNNNNYNNYNNNY",
          138  + "NNNNNNNNNNNNNNNNNYNNNNYNNYNNNY",
          139  + "NNNNNYNNNYNNYNNYNYNNNNYNNNNNYY",
          140  + "NNNNNYNNNYNNNNNNNNNNNNYNNNNNNN",
          141  + "NYNYYNYNYNYNNYYNNNYYYYNYYNYNNN",
          142  + "NNNNNYNNNYNNYNNYYYNNNNYNNNNNNY",
          143  + "NNNNNNNNNNNNNNNYYYNNNNYNNYNNYY",
          144  + "YYYYNNYNYNNNNYYNNNYYNNNNYNYYNN",
          145  + "NNNNNYNNNNNNNNNYNYNNNNYNNYNNYN",
          146  + "NNNNNYNNNNNNNYNYYNNNNNNNNYNNYY",
          147  + "YYNNNNYYYNNYNYYNNNNNYNNNYNYYNN",
          148  + "YYYNNNYNYNYNNYYNNNYYYNNYYNNYNN"};
          149  +   vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
          150  + int _ = 3;
          151  +END
          152  +/*
          153  +CASE(4)
          154  + string color = ;
          155  + string graph_[] = ;
          156  +   vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
          157  + int _ = ;
          158  +END
          159  +CASE(5)
          160  + string color = ;
          161  + string graph_[] = ;
          162  +   vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
          163  + int _ = ;
          164  +END
          165  +*/
          166  +}
          167  +// END CUT HERE

Added SRM/589-U/1C-U.cpp version [ea7a7045ff580752]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class FlippingBitsDiv1 { public:
           23  + int getmin(vector <string> Sv, int M)
           24  + {
           25  +  string S = accumulate(Sv.begin(), Sv.end(), string());
           26  +  vector< vector<int> > Z(M);
           27  +  for(int i=0; i<S.size(); ++i)
           28  +   Z[i%M].push_back(S[i]-'0');
           29  +
           30  +  int best = S.size();
           31  +  if(M <= 16)
           32  +  {
           33  +   for(int mask=0; mask<(1<<M); ++mask)
           34  +   {
           35  +    vector<int> target(M);
           36  +    for(int i=0; i<M; ++i)
           37  +     target[i] = (mask & (1<<i) ? 1 : 0);
           38  +    best = min(best, solve1(Z, target, M));
           39  +   }
           40  +  }
           41  +  else
           42  +  {
           43  +   int X = Z.back().size();
           44  +   for(int mask=0; mask<(1<<X); ++mask)
           45  +   {
           46  +    vector<int> flip_idx;
           47  +    for(int i=0; i<X; ++i)
           48  +     if(mask & (1<<i))
           49  +      flip_idx.push_back(i);
           50  +    best = min(best, solve2(Z, flip_idx, M));
           51  +   }
           52  +  }
           53  +  return best;
           54  + }
           55  +
           56  + int solve1(const vector<vector<int>>& Z, const vector<int>& T, int M)
           57  + {
           58  +  const int X = Z.front().size();
           59  +  vector<int> nc(X+1), fc(X+1);
           60  +  for(int y=0; y<M; ++y)
           61  +  {
           62  +   vector<int> ncy(X+1);
           63  +   vector<int> fcy(X+1);
           64  +   for(int x=0; x<X; ++x) {
           65  +    ncy[x+1] = ncy[x] + (x>=Z[y].size() ? 0 : (Z[y][x]==T[y] ? 0 : 1));
           66  +    fcy[x+1] = fcy[x] + (x>=Z[y].size() ? 0 : (Z[y][x]==T[y] ? 1 : 0));
           67  +    nc[x+1] += ncy[x+1];
           68  +    fc[x+1] += fcy[x+1];
           69  +   }
           70  +  }
           71  +
           72  +  int INF = 999999;
           73  +  vector<vector<int>> dp(X+1, vector<int>(2));
           74  +  enum {N, F};
           75  +  dp[X][N] = INF;
           76  +  dp[X][F] = -1;
           77  +  for(int x=X-1; x>=0; --x)
           78  +  {
           79  +   dp[x][N] = INF;
           80  +   dp[x][F] = INF;
           81  +   for(int q=x+1; q<=X; ++q) {
           82  +    dp[x][N] = min(dp[x][N], 1+dp[q][F]+(nc[q]-nc[x]));
           83  +    dp[x][F] = min(dp[x][F], 1+dp[q][N]+(fc[q]-fc[x]));
           84  +   }
           85  +  }
           86  +  return min(dp[0][N], dp[0][F]);
           87  + }
           88  +
           89  + int solve2(const vector<vector<int>>& Z, const vector<int>& flip_idx, int M)
           90  + {
           91  +  return -178116;
           92  + }
           93  +};
           94  +
           95  +// BEGIN CUT HERE
           96  +#include <ctime>
           97  +double start_time; string timer()
           98  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           99  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          100  + { os << "{ ";
          101  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          102  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          103  +void verify_case(const int& Expected, const int& Received) {
          104  + bool ok = (Expected == Received);
          105  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          106  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          107  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          108  +#define END  verify_case(_, FlippingBitsDiv1().getmin(S, M));}
          109  +int main(){
          110  +
          111  +CASE(0)
          112  + string S_[] = {"00111000"};
          113  +   vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_));
          114  + int M = 1;
          115  + int _ = 2;
          116  +END
          117  +CASE(1)
          118  + string S_[] = {"101100001101"};
          119  +   vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_));
          120  + int M = 3;
          121  + int _ = 2;
          122  +END
          123  +CASE(2)
          124  + string S_[] = {"11111111"};
          125  +   vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_));
          126  + int M = 4;
          127  + int _ = 0;
          128  +END
          129  +CASE(3)
          130  + string S_[] = {"1101001000"};
          131  +   vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_));
          132  + int M = 8;
          133  + int _ = 1;
          134  +END
          135  +CASE(4)
          136  + string S_[] = {"1","10","11","100","101","110"};
          137  +   vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_));
          138  + int M = 5;
          139  + int _ = 4;
          140  +END
          141  +CASE(5)
          142  + string S_[] = {"1001011000101010001111111110111011011100110001001"};
          143  +   vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_));
          144  + int M = 2;
          145  + int _ = 16;
          146  +END
          147  + /*
          148  +CASE(6)
          149  + string S_[] = ;
          150  +   vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_));
          151  + int M = ;
          152  + int _ = ;
          153  +END
          154  +CASE(7)
          155  + string S_[] = ;
          156  +   vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_));
          157  + int M = ;
          158  + int _ = ;
          159  +END
          160  + */
          161  +}
          162  +// END CUT HERE