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

Added SRM/TCO16-2B-U/1A.cpp version [a0907284c078940e]

            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 unsigned MODVAL = 1000000007;
           23  +
           24  +struct mint
           25  +{
           26  + unsigned val;
           27  + mint():val(0){}
           28  + mint(int      x):val(x%MODVAL) {}
           29  + mint(unsigned x):val(x%MODVAL) {}
           30  + mint(LL       x):val(x%MODVAL) {}
           31  +};
           32  +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
           33  +mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
           34  +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
           35  +mint operator+(mint x, mint y) { return x+=y; }
           36  +mint operator-(mint x, mint y) { return x-=y; }
           37  +mint operator*(mint x, mint y) { return x*=y; }
           38  +mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
           39  +mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); }
           40  +mint operator/(mint x, mint y) { return x/=y; }
           41  +
           42  +class TriangleTriples { public:
           43  + int count(int A, int B, int C)
           44  + {
           45  +  return (mint(A)*B*C - cut(A,B,C) - cut(B,C,A) - cut(C,A,B)).val;
           46  + }
           47  +
           48  + // #{(a,b,c)<=(A,B,C) | a+b<=c}
           49  + mint cut(LL A, LL B, LL C)
           50  + {
           51  +  if(A>B) swap(A,B);
           52  +
           53  +  //----------------------------
           54  +  // Sigma
           55  +  // #{a+b <= 1}
           56  +  // #{a+b <= 2}
           57  +  // ...
           58  +  // #{a+b <= C}
           59  +  //----------------------------
           60  +  // Sigma
           61  +  // #{a+b == 1} * C
           62  +  // #{a+b == 2} * C-1
           63  +  // ...
           64  +  // #{a+b == C} * 1
           65  +  //----------------------------
           66  +  // where
           67  +  //
           68  +  //  #{a+b == k}
           69  +  //=
           70  +  //   k-1       for        k <= A
           71  +  //   A         for  A+1<= k <= B
           72  +  //   A-(k-B)+1 for  B+1<= k <= A+B
           73  +  //   0         for  A+B<  k
           74  +  //----------------------------
           75  +
           76  +  mint total = 0;
           77  +
           78  +  //for(int k=1; k<=min(C,A); ++k)
           79  +  // total += mint(k-1) * (C-k+1);
           80  +  {
           81  +   LL x = min(C,A);
           82  +   total += mint(0+x-1)*x/2 * C - mint(x-1)*x*(2*x-1)/6;
           83  +  }
           84  +
           85  +  // for(int k=A+1; k<=min(C,B); ++k)
           86  +  //  total += mint(A) * (C-k+1);
           87  +  if(A+1 <= min(C,B)) {
           88  +   LL x = A+1, y = min(C,B);
           89  +   total += mint(A) * (C-x+1+C-y+1) * (y-x+1) / 2;
           90  +  }
           91  +
           92  +  //for(int k=B+1; k<=min(C,A+B); ++k)
           93  +  // total += mint(A-(k-B)+1) * (C-k+1);
           94  +
           95  +  if(B+1 <= min(C,A+B)) {
           96  +   LL X = min(C,A+B)-B, D = C-B;
           97  +   //for(LL k=0; k<=X; ++k)
           98  +   // total += mint(A-k)*(D-k);
           99  +
          100  +   LL E = abs(D-A);
          101  +   //for(LL k=0; k<=X; ++k)
          102  +   // total += mint(k)*(k+E);
          103  +   total += mint(X)*(X+1)/2*E + mint(X)*(X+1)*(2*X+1)/6;
          104  +  }
          105  +  return total;
          106  + }
          107  +};
          108  +
          109  +// BEGIN CUT HERE
          110  +#include <ctime>
          111  +double start_time; string timer()
          112  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          113  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          114  + { os << "{ ";
          115  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          116  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          117  +void verify_case(const int& Expected, const int& Received) {
          118  + bool ok = (Expected == Received);
          119  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          120  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          121  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          122  +#define END  verify_case(_, TriangleTriples().count(A, B, C));}
          123  +int main(){
          124  +
          125  +CASE(0)
          126  + int A = 1;
          127  + int B = 10;
          128  + int C = 20;
          129  + int _ = 10;
          130  +END
          131  +CASE(2)
          132  + int A = 10;
          133  + int B = 10;
          134  + int C = 10;
          135  + int _ = 505;
          136  +END
          137  +CASE(3)
          138  + int A = 1;
          139  + int B = 1;
          140  + int C = 1;
          141  + int _ = 1;
          142  +END
          143  +CASE(1)
          144  + int A = 2;
          145  + int B = 2;
          146  + int C = 1000000000;
          147  + int _ = 6;
          148  +END
          149  +CASE(4)
          150  + int A = 123456789;
          151  + int B = 987654321;
          152  + int C = 555555555;
          153  + int _ = 64296241;
          154  +END
          155  +CASE(4)
          156  + int A = 123456789;
          157  + int B = 555555555;
          158  + int C = 987654321;
          159  + int _ = 64296241;
          160  +END
          161  +CASE(4)
          162  + int A = 555555555;
          163  + int B = 987654321;
          164  + int C = 123456789;
          165  + int _ = 64296241;
          166  +END
          167  +/*
          168  +CASE(5)
          169  + int A = ;
          170  + int B = ;
          171  + int C = ;
          172  + int _ = ;
          173  +END
          174  +CASE(6)
          175  + int A = ;
          176  + int B = ;
          177  + int C = ;
          178  + int _ = ;
          179  +END
          180  +*/
          181  +}
          182  +// END CUT HERE

Added SRM/TCO16-2B-U/1B-U.cpp version [0875dc7104a617f1]

            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 FoxAndGemstone { public:
           55  + string isPossible(vector <string> bags)
           56  + {
           57  +  set<char> gems;
           58  +  for(auto& bag: bags)
           59  +   for(char gem: bag)
           60  +    gems.insert(gem);
           61  +
           62  +  vector<char> g(gems.begin(), gems.end());
           63  +  do {
           64  +   bool ok = false;
           65  +   for(int x=0; x<bags.size(); ++x) {
           66  +    bool fail = false;
           67  +    for(int y=0; y<bags.size(); ++y) if(x!=y)
           68  +     if(!surely_heavy(bags[x], bags[y], g))
           69  +      fail=true;
           70  +    if(!fail)
           71  +     ok = true;
           72  +   }
           73  +   if(!ok)
           74  +    return "Impossible";
           75  +  } while(next_permutation(g.begin(), g.end()));
           76  +  return "Possible";
           77  + }
           78  +
           79  + // w[a] >= w[b] for sure
           80  + bool surely_heavy(const string& a, const string& b, vector<char> g)
           81  + {
           82  +  if(a.size() < b.size())
           83  +   return false;
           84  +
           85  +  graph G(a.size()+b.size());
           86  +  for(int x=0; x<a.size(); ++x)
           87  +  for(int y=0; y<b.size(); ++y)
           88  +   if(find(g.begin(),g.end(),a[x]) >= find(g.begin(),g.end(),b[y]))
           89  +    G[x].emplace_back(a.size()+y);
           90  +
           91  +  return biMatch<100>(G, a.size()) == b.size();
           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 string& Expected, const string& 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(_, FoxAndGemstone().isPossible(bags));}
          109  +int main(){
          110  +
          111  +CASE(0)
          112  + string bags_[] = {"AB", "AC"};
          113  +   vector <string> bags(bags_, bags_+sizeof(bags_)/sizeof(*bags_));
          114  + string _ = "Possible";
          115  +END
          116  +CASE(1)
          117  + string bags_[] = {"A", "BC"};
          118  +   vector <string> bags(bags_, bags_+sizeof(bags_)/sizeof(*bags_));
          119  + string _ = "Impossible";
          120  +END
          121  +CASE(2)
          122  + string bags_[] = {"A", "B", "C", "AB", "AC", "BC", "ABC"};
          123  +   vector <string> bags(bags_, bags_+sizeof(bags_)/sizeof(*bags_));
          124  + string _ = "Possible";
          125  +END
          126  +CASE(3)
          127  + string bags_[] = {"AB","AC","AD","BC","BD","CD"};
          128  +   vector <string> bags(bags_, bags_+sizeof(bags_)/sizeof(*bags_));
          129  + string _ = "Possible";
          130  +END
          131  +CASE(4)
          132  + string bags_[] = {"AB", "CD"};
          133  +   vector <string> bags(bags_, bags_+sizeof(bags_)/sizeof(*bags_));
          134  + string _ = "Impossible";
          135  +END
          136  +CASE(5)
          137  + string bags_[] = {"A", "A", "A"};
          138  +   vector <string> bags(bags_, bags_+sizeof(bags_)/sizeof(*bags_));
          139  + string _ = "Possible";
          140  +END
          141  +/*
          142  +CASE(6)
          143  + string bags_[] = ;
          144  +   vector <string> bags(bags_, bags_+sizeof(bags_)/sizeof(*bags_));
          145  + string _ = ;
          146  +END
          147  +CASE(7)
          148  + string bags_[] = ;
          149  +   vector <string> bags(bags_, bags_+sizeof(bags_)/sizeof(*bags_));
          150  + string _ = ;
          151  +END
          152  +*/
          153  +}
          154  +// END CUT HERE