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

Added SRM/561-U/1A.cpp version [bf34be831eb65e07]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +class ICPCBalloons { public:
           23  + static const int INF = 0x3fffffff;
           24  +
           25  + int minRepaintings(vector <int> balloonCount, string balloonSize, vector <int> maxAccepted)
           26  + {
           27  +  const int N = balloonCount.size();
           28  +  const int Q = maxAccepted.size();
           29  +
           30  +  vector<int> M, L;
           31  +  for(int i=0; i<N; ++i)
           32  +   (balloonSize[i]=='M' ? M : L).push_back(balloonCount[i]);
           33  +
           34  +  sort(M.rbegin(), M.rend());
           35  +  sort(L.rbegin(), L.rend());
           36  +  sort(maxAccepted.rbegin(), maxAccepted.rend());
           37  +
           38  +  int best = INF;
           39  +
           40  +  for(int m=0; m<(1<<Q); ++m) {
           41  +   vector<int> forM, forL;
           42  +   for(int i=0; i<Q; ++i)
           43  +    (m & (1<<i) ? forM : forL).push_back(maxAccepted[i]);
           44  +   best = min(best, cost(M, forM)+cost(L, forL));
           45  +  }
           46  +  return best==INF ? -1 : best;
           47  + }
           48  +
           49  + int cost(const vector<int>& b, const vector<int> q)
           50  + {
           51  +  int more = 0;
           52  +  int less = 0;
           53  +  for(int i=0; i<q.size(); ++i) {
           54  +   int bi = i<b.size() ? b[i] : 0;
           55  +   if(bi >= q[i]) {
           56  +    more += bi - q[i];
           57  +   } else {
           58  +    less += q[i] - bi;
           59  +   }
           60  +  }
           61  +  for(int i=q.size(); i<b.size(); ++i)
           62  +   more += b[i];
           63  +  return (more>=less ? less : INF);
           64  + }
           65  +};
           66  +
           67  +// BEGIN CUT HERE
           68  +#include <ctime>
           69  +double start_time; string timer()
           70  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           71  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           72  + { os << "{ ";
           73  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           74  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           75  +void verify_case(const int& Expected, const int& Received) {
           76  + bool ok = (Expected == Received);
           77  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           78  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           79  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           80  +#define END  verify_case(_, ICPCBalloons().minRepaintings(balloonCount, balloonSize, maxAccepted));}
           81  +int main(){
           82  +
           83  +CASE(0)
           84  + int balloonCount_[] = {100};
           85  +   vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonCount_)/sizeof(*balloonCount_));
           86  + string balloonSize = "L";
           87  + int maxAccepted_[] = {1,2,3,4,5};
           88  +   vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted_)/sizeof(*maxAccepted_));
           89  + int _ = 10;
           90  +END
           91  +CASE(1)
           92  + int balloonCount_[] = {100};
           93  +   vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonCount_)/sizeof(*balloonCount_));
           94  + string balloonSize = "M";
           95  + int maxAccepted_[] = {10,20,30,40,50};
           96  +   vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted_)/sizeof(*maxAccepted_));
           97  + int _ = -1;
           98  +END
           99  +CASE(2)
          100  + int balloonCount_[] = {5,6,1,5,6,1,5,6,1};
          101  +   vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonCount_)/sizeof(*balloonCount_));
          102  + string balloonSize = "MLMMLMMLM";
          103  + int maxAccepted_[] = {7,7,4,4,7,7};
          104  +   vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted_)/sizeof(*maxAccepted_));
          105  + int _ = 6;
          106  +END
          107  +CASE(3)
          108  + int balloonCount_[] = {100,100};
          109  +   vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonCount_)/sizeof(*balloonCount_));
          110  + string balloonSize = "ML";
          111  + int maxAccepted_[] = {50,51,51};
          112  +   vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted_)/sizeof(*maxAccepted_));
          113  + int _ = -1;
          114  +END
          115  +CASE(4)
          116  + int balloonCount_[] = {8,5,1,4,1,1,3,1,3,3,5,4,5,6,9};
          117  +   vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonCount_)/sizeof(*balloonCount_));
          118  + string balloonSize = "MMMLLLMMLLMLMLM";
          119  + int maxAccepted_[] = {3,5,3,3,5,6,4,6,4,2,3,7,1,5,2};
          120  +   vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted_)/sizeof(*maxAccepted_));
          121  + int _ = 5;
          122  +END
          123  +CASE(5)
          124  + int balloonCount_[] = {1,18,4,7,19,7,7,1,4,8,10,5,14,13,8,22,6,3,13,5,3,4,2,1,3,15,19,4,5,9,4,11,2,7,12,20,11,26,22,7,2,10,9,20,13,20,2,9,11,9};
          125  +   vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonCount_)/sizeof(*balloonCount_));
          126  + string balloonSize = "LLMLLLLMLLLLLLLLLLLLMLLLLLLLLLLMMLMLLLMLLLLLLLLMLL";
          127  + int maxAccepted_[] = {44,59,29,53,16,23,13,14,29,42,13,15,66,4,47};
          128  +   vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted_)/sizeof(*maxAccepted_));
          129  + int _ = 210;
          130  +END
          131  +/*
          132  +CASE(6)
          133  + int balloonCount_[] = ;
          134  +   vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonCount_)/sizeof(*balloonCount_));
          135  + string balloonSize = ;
          136  + int maxAccepted_[] = ;
          137  +   vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted_)/sizeof(*maxAccepted_));
          138  + int _ = ;
          139  +END
          140  +CASE(7)
          141  + int balloonCount_[] = ;
          142  +   vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonCount_)/sizeof(*balloonCount_));
          143  + string balloonSize = ;
          144  + int maxAccepted_[] = ;
          145  +   vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted_)/sizeof(*maxAccepted_));
          146  + int _ = ;
          147  +END
          148  +*/
          149  +}
          150  +// END CUT HERE

Added SRM/561-U/1B-U.cpp version [4f1638dcf4f1be51]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +class CirclesGame { public:
           23  + string whoCanWin(vector <int> x, vector <int> y, vector <int> r)
           24  + {
           25  +  vector< pair<int, pair<int,int> > > xyr;
           26  +  const int N = x.size();
           27  +  for(int i=0; i<N; ++i)
           28  +   xyr.push_back(make_pair(r[i], make_pair(x[i],y[i])));
           29  +  sort(xyr.begin(), xyr.end());
           30  +
           31  +  vector<int> parent(N, -1);
           32  +  for(int i=0; i<N; ++i) {
           33  +   for(int k=i+1; k<N; ++k) {
           34  +    int r1 = xyr[i].first;
           35  +    int x1 = xyr[i].second.first;
           36  +    int y1 = xyr[i].second.second;
           37  +    int r2 = xyr[k].first;
           38  +    int x2 = xyr[k].second.first;
           39  +    int y2 = xyr[k].second.second;
           40  +    if( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) < r2*r2 )
           41  +     {parent[i] = k; break;}
           42  +   }
           43  +  }
           44  +  return solve(N, parent) ? "Bob" : "Alice";
           45  + }
           46  +
           47  + bool solve(int N, const vector<int>& p)
           48  + {
           49  +  vector<int> r;
           50  +  vector< vector<int> > c(N);
           51  +  for(int i=0; i<N; ++i)
           52  +   if(p[i] == -1)
           53  +    r.push_back(i);
           54  +   else
           55  +    c[p[i]].push_back(i);
           56  +
           57  +  memo.assign(N, -1);
           58  +
           59  +  int XOR = 0;
           60  +  for(int i=0; i<r.size(); ++i) {
           61  +   int g = grundy(c, r[i]);
           62  +   XOR ^= g;
           63  +  }
           64  +  return XOR == 0;
           65  + }
           66  +
           67  + vector<int> memo;
           68  + int grundy(const vector< vector<int> >& ch, int v)
           69  + {
           70  +  if(memo[v]!=-1)
           71  +   return memo[v];
           72  +
           73  +  vector<int> next;
           74  +  rec(ch, v, 0, next);
           75  +  return memo[v] = mex(next);
           76  + }
           77  +
           78  + void rec(const vector< vector<int> >& ch, int v, int XOR_acc, vector<int>& next)
           79  + {
           80  +  int XOR = XOR_acc;
           81  +  for(int i=0; i<ch[v].size(); ++i)
           82  +   XOR ^= grundy(ch, ch[v][i]);
           83  +
           84  +  // cut here.
           85  +  next.push_back(XOR);
           86  +  // go below.
           87  +  for(int i=0; i<ch[v].size(); ++i)
           88  +   rec(ch, ch[v][i], XOR^grundy(ch, ch[v][i]), next);
           89  + }
           90  +
           91  + int mex(vector<int>& next)
           92  + {
           93  +  sort(next.begin(), next.end());
           94  +  for(int k=0; k<next.size(); ++k)
           95  +   if( k != next[k] )
           96  +    return k;
           97  +  return next.size();
           98  + }
           99  +};
          100  +
          101  +// BEGIN CUT HERE
          102  +#include <ctime>
          103  +double start_time; string timer()
          104  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          105  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          106  + { os << "{ ";
          107  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          108  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          109  +void verify_case(const string& Expected, const string& Received) {
          110  + bool ok = (Expected == Received);
          111  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          112  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          113  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          114  +#define END  verify_case(_, CirclesGame().whoCanWin(x, y, r));}
          115  +int main(){
          116  +
          117  +CASE(0)
          118  + int x_[] = {0};
          119  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          120  + int y_[] = {0};
          121  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          122  + int r_[] = {1};
          123  +   vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
          124  + string _ = "Alice";
          125  +END
          126  +CASE(1)
          127  + int x_[] = {0, 3};
          128  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          129  + int y_[] = {0, 0};
          130  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          131  + int r_[] = {1, 1};
          132  +   vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
          133  + string _ = "Bob";
          134  +END
          135  +CASE(2)
          136  + int x_[] = {0, 0, 5};
          137  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          138  + int y_[] = {0, 0, 0};
          139  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          140  + int r_[] = {1, 2, 1};
          141  +   vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
          142  + string _ = "Alice";
          143  +END
          144  +CASE(3)
          145  + int x_[] = {0, 0, 0, 10, 10, 20};
          146  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          147  + int y_[] = {0, 0, 0, 0, 0, 0};
          148  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          149  + int r_[] = {1, 2, 3, 1, 2, 1};
          150  +   vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
          151  + string _ = "Bob";
          152  +END
          153  +CASE(4)
          154  + int x_[] = {10,20,30,40,50,60,70,80};
          155  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          156  + int y_[] = {8,7,6,5,4,3,2,1};
          157  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          158  + int r_[] = {2,2,2,2,2,2,2,2};
          159  +   vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
          160  + string _ = "Bob";
          161  +END
          162  +CASE(5)
          163  + int x_[] = {0, 3, 6, 9, 12, -4747, -4777};
          164  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          165  + int y_[] = {-5858, -5858, -5858, -5858, -5858, 777, 777};
          166  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          167  + int r_[] = {58, 1, 1, 1, 1, 44, 8};
          168  +   vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
          169  + string _ = "Bob";
          170  +END
          171  +CASE(6)
          172  + int x_[] = {5202, 5699, -7433, 5068, -9483, -684, -6593, 5108, -7813, 6823, 3267, -8222, -8547, 2878, 2413, 8557, 5149, 5073, -8638, -6108, 8097};
          173  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          174  + int y_[] = {8728, -7407, 4338, -8414, 7652, -3705, -984, 5976, -9180, -9119, 9301, 2398, 7915, 6205, 7665, 717, -9884, 11, -8579, -6903, -746};
          175  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          176  + int r_[] = {4196, 9303, 7152, 5875, 2943, 788, 502, 416, 1958, 3174, 182, 1256, 1147, 444, 979, 65, 1040, 1233, 438, 175, 1140};
          177  +   vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
          178  + string _ = "Alice";
          179  +END
          180  +/*
          181  +CASE(7)
          182  + int x_[] = ;
          183  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          184  + int y_[] = ;
          185  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          186  + int r_[] = ;
          187  +   vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
          188  + string _ = ;
          189  +END
          190  +CASE(8)
          191  + int x_[] = ;
          192  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          193  + int y_[] = ;
          194  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          195  + int r_[] = ;
          196  +   vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
          197  + string _ = ;
          198  +END
          199  +*/
          200  +}
          201  +// END CUT HERE