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

Added SRM/679/1A.cpp version [8502d7bbdeef57a7]

            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 FiringEmployees { public:
           23  + int fire(vector <int> manager, vector <int> salary, vector <int> productivity)
           24  + {
           25  +  const int N = manager.size()+1;
           26  +
           27  +  vector<vector<int>> children(N);
           28  +  for(int i=1; i<N; ++i)
           29  +   children[manager[i-1]].push_back(i);
           30  +
           31  +  vector<int> best(N);
           32  +  for(int i=N-1; i>=0; --i) {
           33  +   int total = (i ? productivity[i-1] - salary[i-1] : 0);
           34  +   for(int u: children[i])
           35  +    total += best[u];
           36  +   if(total > 0)
           37  +    best[i] = total;
           38  +  }
           39  +  return best[0];
           40  + }
           41  +};
           42  +
           43  +// BEGIN CUT HERE
           44  +#include <ctime>
           45  +double start_time; string timer()
           46  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           47  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           48  + { os << "{ ";
           49  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           50  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           51  +void verify_case(const int& Expected, const int& Received) {
           52  + bool ok = (Expected == Received);
           53  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           54  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           55  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           56  +#define END  verify_case(_, FiringEmployees().fire(manager, salary, productivity));}
           57  +int main(){
           58  +
           59  +CASE(0)
           60  + int manager_[] = {0,0,0};
           61  +   vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manager_));
           62  + int salary_[] = {1,2,3};
           63  +   vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_));
           64  + int productivity_[] = {3,2,1};
           65  +   vector <int> productivity(productivity_, productivity_+sizeof(productivity_)/sizeof(*productivity_));
           66  + int _ = 2;
           67  +END
           68  +CASE(1)
           69  + int manager_[] = {0,1,2,3};
           70  +   vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manager_));
           71  + int salary_[] = {4,3,2,1};
           72  +   vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_));
           73  + int productivity_[] = {2,3,4,5};
           74  +   vector <int> productivity(productivity_, productivity_+sizeof(productivity_)/sizeof(*productivity_));
           75  + int _ = 4;
           76  +END
           77  +CASE(2)
           78  + int manager_[] = {0,1};
           79  +   vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manager_));
           80  + int salary_[] = {1,10};
           81  +   vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_));
           82  + int productivity_[] = {5,5};
           83  +   vector <int> productivity(productivity_, productivity_+sizeof(productivity_)/sizeof(*productivity_));
           84  + int _ = 4;
           85  +END
           86  +CASE(3)
           87  + int manager_[] = {0,1,2,1,2,3,4,2,3};
           88  +   vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manager_));
           89  + int salary_[] = {5,3,6,8,4,2,4,6,7};
           90  +   vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_));
           91  + int productivity_[] = {2,5,7,8,5,3,5,7,9};
           92  +   vector <int> productivity(productivity_, productivity_+sizeof(productivity_)/sizeof(*productivity_));
           93  + int _ = 6;
           94  +END
           95  +CASE(4)
           96  + int manager_[] = {0,0,1,1,2,2};
           97  +   vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manager_));
           98  + int salary_[] = {1,1,1,2,2,2};
           99  +   vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_));
          100  + int productivity_[] = {2,2,2,1,1,1};
          101  +   vector <int> productivity(productivity_, productivity_+sizeof(productivity_)/sizeof(*productivity_));
          102  + int _ = 3;
          103  +END
          104  +/*
          105  +CASE(5)
          106  + int manager_[] = ;
          107  +   vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manager_));
          108  + int salary_[] = ;
          109  +   vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_));
          110  + int productivity_[] = ;
          111  +   vector <int> productivity(productivity_, productivity_+sizeof(productivity_)/sizeof(*productivity_));
          112  + int _ = ;
          113  +END
          114  +CASE(6)
          115  + int manager_[] = ;
          116  +   vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manager_));
          117  + int salary_[] = ;
          118  +   vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_));
          119  + int productivity_[] = ;
          120  +   vector <int> productivity(productivity_, productivity_+sizeof(productivity_)/sizeof(*productivity_));
          121  + int _ = ;
          122  +END
          123  +*/
          124  +}
          125  +// END CUT HERE

Added SRM/679/1B.cpp version [88a9946483caf8ed]

            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  +double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); }
           23  +
           24  +bool point_in_polygon( vector<CMP>& ps, CMP p )
           25  +{
           26  + bool in = false;
           27  + for(int i=0; i<ps.size(); ++i) {
           28  +  CMP a = ps[i] - p;
           29  +  CMP b = ps[(i+1)%ps.size()] - p;
           30  +  if(a.imag() > b.imag()) swap(a,b);
           31  +  if(a.imag()<=0 && 0<b.imag()) {
           32  +   if( outer_prod(a,b) < 0 )
           33  +    in = !in;
           34  +  }
           35  + }
           36  + return in;
           37  +}
           38  +
           39  +class RedAndBluePoints { public:
           40  + int find(vector <int> blueX, vector <int> blueY, vector <int> redX, vector <int> redY)
           41  + {
           42  +  const int B = blueX.size();
           43  +  const int R = redX.size();
           44  +
           45  +  int best = 0;
           46  +  for(int b_use=0; b_use<B; ++b_use)
           47  +  {
           48  +   vector<vector<int>> G(B);
           49  +   for(int b1=0; b1<B; ++b1) if(b1 != b_use)
           50  +   for(int b2=b1+1; b2<B; ++b2) if(b2 != b_use) {
           51  +    bool bad = false;
           52  +
           53  +    vector<CMP> poly;
           54  +    poly.emplace_back(blueX[b_use], blueY[b_use]);
           55  +    poly.emplace_back(blueX[b1], blueY[b1]);
           56  +    poly.emplace_back(blueX[b2], blueY[b2]);
           57  +    for(int r=0; r<R; ++r)
           58  +     if(point_in_polygon(poly, CMP(redX[r], redY[r])))
           59  +      { bad=true; break; }
           60  +
           61  +    if(bad) {
           62  +     G[b1].push_back(b2);
           63  +     G[b2].push_back(b1);
           64  +    }
           65  +   }
           66  +   best = max(best, max_independent_set(G));
           67  +  }
           68  +  return best;
           69  + }
           70  +
           71  + int max_independent_set(const vector<vector<int>>& G)
           72  + {
           73  +  const int N = G.size();
           74  +  vector<LL> badmask(G.size());
           75  +  for(int v=0; v<N; ++v) {
           76  +   LL x = 1LL<<v;
           77  +   for(int u: G[v])
           78  +    x |= 1LL<<u;
           79  +   badmask[v] = x;
           80  +  }
           81  +
           82  +  int best = 0;
           83  +  function<void(int,LL,int)> rec = [&](int v, LL rest, int cur) {
           84  +   if(best < cur)
           85  +    best = cur;
           86  +   if(rest == 0)
           87  +    return;
           88  +   if(cur + __builtin_popcountll(rest) <= best)
           89  +    return;
           90  +
           91  +   LL r1 = rest &~ (1LL<<v);
           92  +   LL r2 = rest &~ badmask[v];
           93  +   if(rest & (1LL<<v)) {
           94  +    if(r1 != r2) rec(v+1, r1, cur);
           95  +    rec(v+1, r2, cur+1);
           96  +   } else {
           97  +    rec(v+1, r1, cur);
           98  +   }
           99  +  };
          100  +  rec(0, (1LL<<N)-1, 0);
          101  +  return best;
          102  + }
          103  +};
          104  +
          105  +// BEGIN CUT HERE
          106  +#include <ctime>
          107  +double start_time; string timer()
          108  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          109  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          110  + { os << "{ ";
          111  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          112  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          113  +void verify_case(const int& Expected, const int& Received) {
          114  + bool ok = (Expected == Received);
          115  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          116  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          117  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          118  +#define END  verify_case(_, RedAndBluePoints().find(blueX, blueY, redX, redY));}
          119  +int main(){
          120  +
          121  +CASE(0)
          122  + int blueX_[] = {0,0,10,10};
          123  +   vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_));
          124  + int blueY_[] = {0,10,0,10};
          125  +   vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_));
          126  + int redX_[] = {100};
          127  +   vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_));
          128  + int redY_[] = {120};
          129  +   vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_));
          130  + int _ = 4;
          131  +END
          132  +CASE(1)
          133  + int blueX_[] = {0,0,10,10};
          134  +   vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_));
          135  + int blueY_[] = {0,10,0,10};
          136  +   vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_));
          137  + int redX_[] = {3};
          138  +   vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_));
          139  + int redY_[] = {4};
          140  +   vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_));
          141  + int _ = 3;
          142  +END
          143  +CASE(2)
          144  + int blueX_[] = {0,0,10,10};
          145  +   vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_));
          146  + int blueY_[] = {0,10,0,10};
          147  +   vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_));
          148  + int redX_[] = {3,6};
          149  +   vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_));
          150  + int redY_[] = {2,7};
          151  +   vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_));
          152  + int _ = 2;
          153  +END
          154  +CASE(3)
          155  + int blueX_[] = {0};
          156  +   vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_));
          157  + int blueY_[] = {0};
          158  +   vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_));
          159  + int redX_[] = {1};
          160  +   vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_));
          161  + int redY_[] = {1};
          162  +   vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_));
          163  + int _ = 1;
          164  +END
          165  +CASE(4)
          166  + int blueX_[] = {5, 6, 6};
          167  +   vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_));
          168  + int blueY_[] = {9, 0, 5};
          169  +   vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_));
          170  + int redX_[] = {7};
          171  +   vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_));
          172  + int redY_[] = {6};
          173  +   vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_));
          174  + int _ = 3;
          175  +END
          176  +/*
          177  +CASE(5)
          178  + int blueX_[] = ;
          179  +   vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_));
          180  + int blueY_[] = ;
          181  +   vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_));
          182  + int redX_[] = ;
          183  +   vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_));
          184  + int redY_[] = ;
          185  +   vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_));
          186  + int _ = ;
          187  +END
          188  +CASE(6)
          189  + int blueX_[] = ;
          190  +   vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_));
          191  + int blueY_[] = ;
          192  +   vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_));
          193  + int redX_[] = ;
          194  +   vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_));
          195  + int redY_[] = ;
          196  +   vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_));
          197  + int _ = ;
          198  +END
          199  +*/
          200  +}
          201  +// END CUT HERE

Added SRM/679/1C.cpp version [9a8c214df95651f4]

            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  +static const int MODVAL = 1000000007;
           23  +class BagAndCards { public:
           24  + int getHash(int n, int m, int x, int a, int b, int c, string isGood)
           25  + {
           26  +  vector<vector<int>> count(n, vector<int>(m, 0));
           27  +  for(int i=0; i<n; ++i)
           28  +  for(int j=0; j<m; ++j) {
           29  +   count[i][j] = x;
           30  +   x = int(((LL(x) * a + b) ^ c) % MODVAL);
           31  +  }
           32  +
           33  +  int total_ans = 0;
           34  +  for(int i=0; i<n; ++i)
           35  +  {
           36  +   vector<LL> mult(m);
           37  +   for(int c1=0; c1<m; ++c1)
           38  +   for(int c2=0; c2<m; ++c2)
           39  +    if(isGood[c1+c2]=='Y')
           40  +     mult[c2] += count[i][c1];
           41  +   for(int c=0; c<m; ++c)
           42  +    mult[c] %= MODVAL;
           43  +
           44  +   for(int k=i+1; k<n; ++k)
           45  +   {
           46  +    LL ans = 0;
           47  +    for(int c=0; c<m; ++c)
           48  +     ans += count[k][c] * mult[c] % MODVAL;
           49  +    total_ans ^= int(ans % MODVAL);
           50  +   }
           51  +  }
           52  +  return total_ans;
           53  + }
           54  +};
           55  +
           56  +// BEGIN CUT HERE
           57  +#include <ctime>
           58  +double start_time; string timer()
           59  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           60  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           61  + { os << "{ ";
           62  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           63  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           64  +void verify_case(const int& Expected, const int& Received) {
           65  + bool ok = (Expected == Received);
           66  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           67  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           68  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           69  +#define END  verify_case(_, BagAndCards().getHash(n, m, x, a, b, c, isGood));}
           70  +int main(){
           71  +
           72  +CASE(0)
           73  + int n = 2;
           74  + int m = 4;
           75  + int x = 1;
           76  + int a = 1;
           77  + int b = 0;
           78  + int c = 0;
           79  + string isGood = "NNYYNYN";
           80  + int _ = 9;
           81  +END
           82  +CASE(1)
           83  + int n = 3;
           84  + int m = 5;
           85  + int x = 1;
           86  + int a = 1;
           87  + int b = 1;
           88  + int c = 2;
           89  + string isGood = "NNYYNYNYN";
           90  + int _ = 1532;
           91  +END
           92  +CASE(2)
           93  + int n = 10;
           94  + int m = 20;
           95  + int x = 111;
           96  + int a = 222;
           97  + int b = 333;
           98  + int c = 444;
           99  + string isGood = "NNNNNYYYNNNYYYYYYNNYYYYNNNNYNNYYYNNNYYN" ;
          100  + int _ = 450750683;
          101  +END
          102  +CASE(3)
          103  + int n = 2;
          104  + int m = 2;
          105  + int x = 1;
          106  + int a = 1;
          107  + int b = 0;
          108  + int c = 0;
          109  + string isGood = "NNY";
          110  + int _ = 1;
          111  +END
          112  +/*
          113  +CASE(4)
          114  + int n = ;
          115  + int m = ;
          116  + int x = ;
          117  + int a = ;
          118  + int b = ;
          119  + int c = ;
          120  + string isGood = ;
          121  + int _ = ;
          122  +END
          123  +CASE(5)
          124  + int n = ;
          125  + int m = ;
          126  + int x = ;
          127  + int a = ;
          128  + int b = ;
          129  + int c = ;
          130  + string isGood = ;
          131  + int _ = ;
          132  +END
          133  +*/
          134  +}
          135  +// END CUT HERE

Added lib/graph/maxIndependentSet.cpp version [d654c32e904bdfb1]

            1  +//-------------------------------------------------------------
            2  +// Bruteforuce O(2^V) search with trivial edagari.
            3  +//
            4  +// |V| must be <= 63
            5  +//
            6  +// Verified by
            7  +//   - SRM 679 Div1 Lv2
            8  +//-------------------------------------------------------------
            9  +
           10  +int max_independent_set(const vector<vector<int>>& G)
           11  +{
           12  + const int N = G.size();
           13  + vector<LL> badmask(G.size());
           14  + for(int v=0; v<N; ++v) {
           15  +  LL x = 1LL<<v;
           16  +  for(int u: G[v])
           17  +   x |= 1LL<<u;
           18  +  badmask[v] = x;
           19  + }
           20  +
           21  + int best = 0;
           22  + function<void(int,LL,int)> rec = [&](int v, LL rest, int cur) {
           23  +  if(best < cur)
           24  +   best = cur;
           25  +  if(rest == 0)
           26  +   return;
           27  +  if(cur + __builtin_popcountll(rest) <= best)
           28  +   return;
           29  +
           30  +  LL r1 = rest &~ (1LL<<v);
           31  +  LL r2 = rest &~ badmask[v];
           32  +  if(rest & (1LL<<v)) {
           33  +   if(r1 != r2) rec(v+1, r1, cur);
           34  +   rec(v+1, r2, cur+1);
           35  +  } else {
           36  +   rec(v+1, r1, cur);
           37  +  }
           38  + };
           39  + rec(0, (1LL<<N)-1, 0);
           40  + return best;
           41  +}