Overview
| SHA1 Hash: | fbe763b30ebfa6e73a66285bcf3caa505d931ac0 |
|---|---|
| Date: | 2016-05-26 13:33:22 |
| User: | kinaba |
| Comment: | 2B |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
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) > 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 > 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() > 120 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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( > 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) > 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 > 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() > 106 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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