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

Added SRM/505-u/1Au.cpp version [9979db28a5ab5334]

            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 <cstring>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class RectangleArea { public:
           23  + int minimumQueries(vector <string> known)
           24  + {
           25  +  const int H = known.size();
           26  +  const int W = known[0].size();
           27  +  for(int y=0; y<H; ++y)
           28  +  for(int x=0; x<W; ++x)
           29  +  for(int Y=0; Y<H; ++Y)
           30  +  for(int X=0; X<W; ++X)
           31  +  if( make_pair(y,x) < make_pair(Y,X) && y!=Y && x!=X )
           32  +  if( known[y][x]=='Y' && known[Y][X]=='Y' )
           33  +  {
           34  +   if( known[y][X]=='Y' )
           35  +    known[Y][x] = 'Y';
           36  +   if( known[Y][x]=='Y' )
           37  +    known[y][X] = 'Y';
           38  +  }
           39  +
           40  +  int tt = 0;
           41  +  for(int i=0; i<W; ++i)
           42  +   if( known[0][i]=='N' )
           43  +    ++tt;
           44  +  int yy = 0;
           45  +  for(int i=0; i<H; ++i)
           46  +   if( known[i][0]=='N' )
           47  +    ++yy;
           48  +  if( tt == 0 )
           49  +   return yy;
           50  +  if( yy == 0 )
           51  +   return tt;
           52  +  return -1;
           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(_, RectangleArea().minimumQueries(known));}
           70  +int main(){
           71  +
           72  +CASE(0)
           73  + string known_[] = {"NN",
           74  + "NN"};
           75  +   vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_));
           76  + int _ = 3;
           77  +END
           78  +CASE(1)
           79  + string known_[] = {"YNY",
           80  + "NYN",
           81  + "YNY"};
           82  +   vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_));
           83  + int _ = 1;
           84  +END
           85  +CASE(2)
           86  + string known_[] = {"YY",
           87  + "YY",
           88  + "YY",
           89  + "YY"};
           90  +   vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_));
           91  + int _ = 0;
           92  +END
           93  +CASE(3)
           94  + string known_[] = {"NNNNNNNNNN"};
           95  +   vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_));
           96  + int _ = 10;
           97  +END
           98  +CASE(4)
           99  + string known_[] = {"NNYYYNN",
          100  + "NNNNNYN",
          101  + "YYNNNNY",
          102  + "NNNYNNN",
          103  + "YYNNNNY"};
          104  +   vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_));
          105  + int _ = 2;
          106  +END
          107  +CASE(5)
          108  + string known_[] = {
          109  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          110  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          111  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          112  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          113  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          114  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          115  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          116  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          117  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          118  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          119  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          120  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          121  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          122  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          123  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          124  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          125  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          126  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          127  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          128  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          129  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          130  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          131  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          132  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          133  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          134  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          135  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          136  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          137  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          138  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          139  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          140  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          141  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          142  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          143  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          144  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          145  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          146  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          147  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          148  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          149  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          150  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          151  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          152  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          153  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          154  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          155  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          156  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          157  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          158  +  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          159  + };
          160  +   vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_));
          161  + int _ = -1;
          162  +END
          163  +CASE(6)
          164  + string known_[] = {"N"};
          165  +   vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_));
          166  + int _ = 1;
          167  +END
          168  +
          169  +}
          170  +// END CUT HERE

Added SRM/505-u/1B.cpp version [dc8b7855f7fb41f0]

            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 <cstring>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class SetMultiples { public:
           23  + long long smallestSubset(long long A, long long B, long long C, long long D)
           24  + {
           25  +  vector< pair<LL,LL> > noneed( 1, make_pair(1,100000) );
           26  +
           27  +  LL cnt = 0;
           28  +  for(LL p=1; p<=100000; ++p)
           29  +  {
           30  +   if( A<=p&&p<=B || C<=p&&p<=D )
           31  +    if( need(p, A, B, C, D) )
           32  +     ++cnt;
           33  +   if( p > 1 ) {
           34  +    add(noneed, p, A, B);
           35  +    add(noneed, p, C, D);
           36  +   }
           37  +  }
           38  +  sort(noneed.begin(), noneed.end(), &my_order);
           39  +  LL a = count_need(noneed, A, B);
           40  +  LL b = count_need(noneed, C, D);
           41  +  return cnt + a + b;
           42  + }
           43  +
           44  + static bool need(LL p, LL A, LL B, LL C, LL D)
           45  + {
           46  +  return !covered(p,A,B) && !covered(p,C,D);
           47  + }
           48  +
           49  + static bool covered(LL p, LL A, LL B)
           50  + {
           51  +  LL lo = A%p==0 ? A/p : A/p+1;
           52  +  LL hi = B/p;
           53  +  return ( lo<=hi && 2<=hi );
           54  + }
           55  +
           56  + static void add(vector< pair<LL,LL> >& noneed, LL p, LL A, LL B)
           57  + {
           58  +  LL lo = A%p==0 ? A/p : A/p+1;
           59  +  LL hi = B/p;
           60  +  if( lo <= hi )
           61  +   noneed.push_back( make_pair(lo,hi) );
           62  + }
           63  +
           64  + static bool my_order( const pair<LL,LL>& lhs, const pair<LL,LL>& rhs )
           65  + {
           66  +  if( lhs.second != rhs.second )
           67  +   return lhs.second > rhs.second;
           68  +  return lhs.first < rhs.first;
           69  + }
           70  +
           71  + static LL count_need(const vector< pair<LL,LL> >& noneed, LL A, LL B)
           72  + {
           73  +  LL cnt = 0;
           74  +  LL highest_need = B;
           75  +  for(int i=0; i<noneed.size(); ++i)
           76  +  {
           77  +   LL lo = noneed[i].first;
           78  +   LL hi = noneed[i].second;
           79  +   if( hi < highest_need )
           80  +    cnt += max(0LL, highest_need - max(hi,A-1));
           81  +   highest_need = min(highest_need, lo-1);
           82  +   if( highest_need < A )
           83  +    return cnt;
           84  +  }
           85  +  return cnt + (highest_need - A + 1);
           86  + }
           87  +};
           88  +
           89  +// BEGIN CUT HERE
           90  +#include <ctime>
           91  +double start_time; string timer()
           92  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           93  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           94  + { os << "{ ";
           95  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           96  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           97  +void verify_case(const long long& Expected, const long long& Received) {
           98  + bool ok = (Expected == Received);
           99  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          100  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          101  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          102  +#define END  verify_case(_, SetMultiples().smallestSubset(A, B, C, D));}
          103  +int main(){
          104  +
          105  +CASE(0)
          106  + long long A = 1LL;
          107  + long long B = 1LL;
          108  + long long C = 2LL;
          109  + long long D = 2LL;
          110  + long long _ = 1LL;
          111  +END
          112  +CASE(1)
          113  + long long A = 1LL;
          114  + long long B = 2LL;
          115  + long long C = 3LL;
          116  + long long D = 4LL;
          117  + long long _ = 2LL;
          118  +END
          119  +CASE(2)
          120  + long long A = 2LL;
          121  + long long B = 3LL;
          122  + long long C = 5LL;
          123  + long long D = 7LL;
          124  + long long _ = 3LL;
          125  +END
          126  +CASE(3)
          127  + long long A = 1LL;
          128  + long long B = 10LL;
          129  + long long C = 100LL;
          130  + long long D = 1000LL;
          131  + long long _ = 500LL;
          132  +END
          133  +CASE(4)
          134  + long long A = 1000000000LL;
          135  + long long B = 2000000000LL;
          136  + long long C = 9000000000LL;
          137  + long long D = 10000000000LL;
          138  + long long _ = 1254365078LL;
          139  +END
          140  +CASE(5)
          141  + long long A = 1LL;
          142  + long long B = 1000000000LL;
          143  + long long C = 2000000000LL;
          144  + long long D = 10000000000LL;
          145  + long long _ = -1LL;
          146  +END
          147  +CASE(6)
          148  + long long A = 1LL;
          149  + long long B = 2LL;
          150  + long long C = 3LL;
          151  + long long D = 5LL;
          152  + long long _ = 3LL;
          153  +END
          154  +
          155  +}
          156  +// END CUT HERE