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

Added SRM/573-U/1A-U.cpp version [1662779681209416]

            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 TeamContest { public:
           23  + int worstRank(vector <int> s)
           24  + {
           25  +  int N = s.size()/3;
           26  +  int us = str(s[0], s[1], s[2]);
           27  +  sort(s.begin()+3, s.end());
           28  +  int L = 0;   // |<=us| <= 0 is impossible
           29  +  int R = N-1; // |<=us| <= N-1 is possible
           30  +  while(R-L>1)
           31  +  {
           32  +   int C = (L+R)/2;
           33  +   (possible(us, C, s) ? R : L) = C;
           34  +  }
           35  +  return N-R;
           36  + }
           37  +
           38  + int str(int a, int b, int c)
           39  + {
           40  +  return max(max(a,b),c) + min(min(a,b),c);
           41  + }
           42  +
           43  + // |<=us| <= UB possible?
           44  + bool possible(int us, int UB, const vector<int>& s)
           45  + {
           46  +  int si = 3;
           47  +
           48  +  // from weak teams
           49  +  while(UB > 0) {
           50  +   if(si==s.size())
           51  +    return true;
           52  +   si += 3;
           53  +   --UB;
           54  +  }
           55  +
           56  +  if(si==s.size())
           57  +   return true; // no more team left
           58  +
           59  +  // can we make every other teams stronger than ourselves?
           60  +  vector<int> ss(s.begin()+si, s.end());
           61  +  while(!ss.empty())
           62  +   if(!takeOut(us, ss))
           63  +    return false;
           64  +  return true;
           65  + }
           66  +
           67  + bool takeOut(int us, vector<int>& s)
           68  + {
           69  +  int a = s[0];
           70  +  s.erase(s.begin());
           71  +  int b = s[0];
           72  +  s.erase(s.begin());
           73  +  for(int i=0; i<s.size(); ++i) {
           74  +   int c = s[i];
           75  +   if(str(a,b,c) > us) {
           76  +    s.erase(s.begin()+i);
           77  +    return true;
           78  +   }
           79  +  }
           80  +  return false;
           81  + }
           82  +};
           83  +
           84  +// BEGIN CUT HERE
           85  +#include <ctime>
           86  +double start_time; string timer()
           87  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           88  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           89  + { os << "{ ";
           90  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           91  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           92  +void verify_case(const int& Expected, const int& Received) {
           93  + bool ok = (Expected == Received);
           94  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           95  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           96  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           97  +#define END  verify_case(_, TeamContest().worstRank(strength));}
           98  +int main(){
           99  +
          100  +CASE(0)
          101  + int strength_[] = {5, 7, 3, 5, 7, 3, 5, 7, 3};
          102  +   vector <int> strength(strength_, strength_+sizeof(strength_)/sizeof(*strength_));
          103  + int _ = 2;
          104  +END
          105  +CASE(1)
          106  + int strength_[] = {5, 7, 3}
          107  +;
          108  +   vector <int> strength(strength_, strength_+sizeof(strength_)/sizeof(*strength_));
          109  + int _ = 1;
          110  +END
          111  +CASE(2)
          112  + int strength_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
          113  +   vector <int> strength(strength_, strength_+sizeof(strength_)/sizeof(*strength_));
          114  + int _ = 1;
          115  +END
          116  +CASE(3)
          117  + int strength_[] = {3,9,4,6,2,6,1,6,9,1,4,1,3,8,5}
          118  +;
          119  +   vector <int> strength(strength_, strength_+sizeof(strength_)/sizeof(*strength_));
          120  + int _ = 3;
          121  +END
          122  +CASE(4)
          123  + int strength_[] = {53,47,88,79,99,75,28,54,65,14,22,13,11,31,43}
          124  +;
          125  +   vector <int> strength(strength_, strength_+sizeof(strength_)/sizeof(*strength_));
          126  + int _ = 3;
          127  +END
          128  +CASE(5)
          129  + int strength_[] = {2,2,2,1,1,1,1,1,5};
          130  +   vector <int> strength(strength_, strength_+sizeof(strength_)/sizeof(*strength_));
          131  + int _ = 2;
          132  +END
          133  +/*
          134  +CASE(6)
          135  + int strength_[] = ;
          136  +   vector <int> strength(strength_, strength_+sizeof(strength_)/sizeof(*strength_));
          137  + int _ = ;
          138  +END
          139  +*/
          140  +}
          141  +// END CUT HERE

Added SRM/573-U/1B.cpp version [58e82fd59ea2f53d]

            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 SkiResorts { public:
           23  + long long minCost(vector <string> road, vector <int> altitude)
           24  + {
           25  +  typedef int Vert;
           26  +  typedef int Alt;
           27  +  typedef pair<Vert,Alt> State;
           28  +  typedef LL Cost;
           29  +  typedef pair<Cost,State> Edge;
           30  +  const int N = altitude.size();
           31  +
           32  +  priority_queue< Edge, vector<Edge>, greater<Edge> > Q;
           33  +  set<State> V;
           34  +  for(int i=0; i<N; ++i) {
           35  +   State init(0, altitude[i]);
           36  +   Q.push( Edge(abs(altitude[i]-altitude[0]), init) );
           37  +  }
           38  +  while( !Q.empty() ) {
           39  +   Cost  c = Q.top().first;
           40  +   State s = Q.top().second;
           41  +   Vert v  = s.first;
           42  +   Alt  vh = s.second;
           43  +   Q.pop();
           44  +   if( V.count(s) )
           45  +    continue;
           46  +   V.insert(s);
           47  +   if( v == N-1 )
           48  +    return c;
           49  +
           50  +   for(Vert u=0; u<N; ++u) if(road[v][u] =='Y') {
           51  +    Alt uh = altitude[u];
           52  +    for(int i=0; i<N; ++i) {
           53  +     Alt ch = altitude[i];
           54  +     if( ch <= vh ) {
           55  +      Cost cc = c + abs(ch-uh);
           56  +      State ss(u, ch);
           57  +      if(!V.count(ss))
           58  +       Q.push(Edge(cc,ss));
           59  +     }
           60  +    }
           61  +   }
           62  +  }
           63  +  return -1;
           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 long long& Expected, const long long& 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(_, SkiResorts().minCost(road, altitude));}
           81  +int main(){
           82  +CASE(0)
           83  + string road_[] = {"NYN",
           84  + "YNY",
           85  + "NYN"};
           86  +   vector <string> road(road_, road_+sizeof(road_)/sizeof(*road_));
           87  + int altitude_[] = {30, 20, 10};
           88  +   vector <int> altitude(altitude_, altitude_+sizeof(altitude_)/sizeof(*altitude_));
           89  + long long _ = 0LL;
           90  +END
           91  +CASE(1)
           92  + string road_[] = {"NY",
           93  + "YN"};
           94  +   vector <string> road(road_, road_+sizeof(road_)/sizeof(*road_));
           95  + int altitude_[] = {10, 20};
           96  +   vector <int> altitude(altitude_, altitude_+sizeof(altitude_)/sizeof(*altitude_));
           97  + long long _ = 10LL;
           98  +END
           99  +CASE(2)
          100  + string road_[] = {"NYN",
          101  + "YNN",
          102  + "NNN"};
          103  +   vector <string> road(road_, road_+sizeof(road_)/sizeof(*road_));
          104  + int altitude_[] = {573, 573, 573};
          105  +   vector <int> altitude(altitude_, altitude_+sizeof(altitude_)/sizeof(*altitude_));
          106  + long long _ = -1LL;
          107  +END
          108  +CASE(3)
          109  + string road_[] = {"NNYNNYYYNN",
          110  + "NNNNYNYNNN",
          111  + "YNNNNYYNNN",
          112  + "NNNNNNYNYY",
          113  + "NYNNNNNNYY",
          114  + "YNYNNNNYNN",
          115  + "YYYYNNNYNN",
          116  + "YNNNNYYNNN",
          117  + "NNNYYNNNNN",
          118  + "NNNYYNNNNN"};
          119  +   vector <string> road(road_, road_+sizeof(road_)/sizeof(*road_));
          120  + int altitude_[] = {7, 4, 13, 2, 8, 1, 8, 15, 5, 15};
          121  +   vector <int> altitude(altitude_, altitude_+sizeof(altitude_)/sizeof(*altitude_));
          122  + long long _ = 12LL;
          123  +END
          124  +CASE(4)
          125  + string road_[] = {
          126  +  "NYNNNNNN",
          127  +  "YNYNNNNN",
          128  +  "NYNYNNNN",
          129  +  "NNYNYNNN",
          130  +  "NNNYNYNN",
          131  +  "NNNNYNYN",
          132  +  "NNNNNYNY",
          133  +  "NNNNNNYN"
          134  + };
          135  +   vector <string> road(road_, road_+sizeof(road_)/sizeof(*road_));
          136  +   int altitude_[] = {
          137  +    1,2,3,3,3,3,3,3
          138  +   };
          139  +   vector <int> altitude(altitude_, altitude_+sizeof(altitude_)/sizeof(*altitude_));
          140  + long long _ = 3LL;
          141  +END
          142  +/*
          143  +CASE(5)
          144  + string road_[] = ;
          145  +   vector <string> road(road_, road_+sizeof(road_)/sizeof(*road_));
          146  + int altitude_[] = ;
          147  +   vector <int> altitude(altitude_, altitude_+sizeof(altitude_)/sizeof(*altitude_));
          148  + long long _ = LL;
          149  +END
          150  +*/
          151  +}
          152  +// END CUT HERE