Overview
| SHA1 Hash: | e73fe40bab05d5074ae92fe4c2f994e4a7f7e7de |
|---|---|
| Date: | 2015-03-09 12:34:14 |
| User: | kinaba |
| Comment: | 650 |
| 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/650-U/1A.cpp version [2ee706699e24611b]
> 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 struct mint > 24 { > 25 unsigned val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} > 28 mint(unsigned x):val(x%MODVAL) {} > 29 mint(LL x):val(x%MODVAL) {} > 30 }; > 31 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } > 32 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } > 33 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 34 mint operator+(mint x, mint y) { return x+=y; } > 35 mint operator-(mint x, mint y) { return x-=y; } > 36 mint operator*(mint x, mint y) { return x*=y; } > 37 > 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 TaroFillingAStringDiv1 { public: > 43 int getNumber(int, vector <int> position, string value) > 44 { > 45 vector<pair<int,char>> sorted; > 46 for(int i=0; i<position.size(); ++i) > 47 sorted.emplace_back(position[i]-1, value[i]); > 48 sort(sorted.begin(), sorted.end()); > 49 > 50 mint ans = 1; > 51 for(int i=1; i<sorted.size(); ++i) > 52 ans *= solve(sorted[i].first-sorted[i-1].first-1, sorted > 53 return ans.val; > 54 } > 55 > 56 // 'A' + '?'*N + (same?'A':'B') > 57 mint solve(int N, bool same) { > 58 if(same && (N%2)==1) > 59 return 1; > 60 if(!same && (N%2)==0) > 61 return 1; > 62 return (N+1); > 63 } > 64 }; > 65 > 66 // BEGIN CUT HERE > 67 #include <ctime> > 68 double start_time; string timer() > 69 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 70 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 71 { os << "{ "; > 72 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 73 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 74 void verify_case(const int& Expected, const int& Received) { > 75 bool ok = (Expected == Received); > 76 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 77 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 78 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 79 #define END verify_case(_, TaroFillingAStringDiv1().getNumber(N, position, > 80 int main(){ > 81 > 82 CASE(0) > 83 int N = 3; > 84 int position_[] = {1, 3}; > 85 vector <int> position(position_, position_+sizeof(position_)/sizeof(*p > 86 string value = "AB"; > 87 int _ = 2; > 88 END > 89 CASE(1) > 90 int N = 4; > 91 int position_[] = {2, 1, 3, 4}; > 92 vector <int> position(position_, position_+sizeof(position_)/sizeof(*p > 93 string value = "ABBA"; > 94 int _ = 1; > 95 END > 96 CASE(2) > 97 int N = 25; > 98 int position_[] = {23, 4, 8, 1, 24, 9, 16, 17, 6, 2, 25, 15, 14, 7, 13}; > 99 vector <int> position(position_, position_+sizeof(position_)/sizeof(*p > 100 string value = "ABBBBABABBAAABA"; > 101 int _ = 1; > 102 END > 103 CASE(3) > 104 int N = 305; > 105 int position_[] = {183, 115, 250, 1, 188, 193, 163, 221, 144, 191, 92, 1 > 106 vector <int> position(position_, position_+sizeof(position_)/sizeof(*p > 107 string value = "ABAABBABBAABABBBBAAAABBABBBA"; > 108 int _ = 43068480; > 109 END > 110 CASE(4) > 111 int N = 1000000000; > 112 int position_[] = {183, 115, 250, 1, 188, 193, 163, 221, 144, 191, 92, 1 > 113 vector <int> position(position_, position_+sizeof(position_)/sizeof(*p > 114 string value = "ABAABBABBAABABBBBAAAABBABBBA"; > 115 int _ = -1; > 116 END > 117 /* > 118 CASE(5) > 119 int N = ; > 120 int position_[] = ; > 121 vector <int> position(position_, position_+sizeof(position_)/sizeof(*p > 122 string value = ; > 123 int _ = ; > 124 END > 125 */ > 126 } > 127 // END CUT HERE
Added SRM/650-U/1B-U.cpp version [fc06f1f14b091ef5]
> 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 class TheKingsRoadsDiv1 { public: > 23 string getAnswer(int h, vector <int> a, vector <int> b) > 24 { > 25 return solve(h, a, b) ? "Correct" : "Incorrect"; > 26 } > 27 > 28 bool solve(int h, const vector<int>& a, const vector<int>& b) > 29 { > 30 // remove obvious abnormality > 31 set<pair<int,int>> e; > 32 for(int i=0; i<a.size(); ++i) > 33 if(a[i] != b[i]) > 34 e.emplace(min(a[i]-1, b[i]-1), max(a[i]-1,b[i]-1 > 35 > 36 if(e.size()+3 < a.size()) > 37 return false; > 38 > 39 const int added = e.size() - ((1<<h)-2); > 40 const int N = (1<<h)-1; > 41 vector<vector<int>> g(N); > 42 for(auto ab: e) { > 43 g[ab.first].emplace_back(ab.second); > 44 g[ab.second].emplace_back(ab.first); > 45 } > 46 > 47 set<pair<int,int>> susp_edges = e; > 48 > 49 vector<int> det_height(N, 0); > 50 vector<vector<int>> det_child(N); > 51 vector<int> det_parent(N, -1); > 52 vector<int> Q; > 53 for(int v=0; v<N; ++v) { > 54 if(g[v].empty()) > 55 return false; > 56 if(g[v].size() == 1) { > 57 det_height[v] = 1; > 58 Q.emplace_back(g[v].front()); > 59 } > 60 } > 61 > 62 for(int dh=2; dh<=h; ++dh) { > 63 vector<int> Q2; > 64 for(int v: Q) { > 65 if(det_height[v] == dh) > 66 continue; > 67 else if(det_height[v] == 0) { > 68 det_height[v] = dh; > 69 vector<int> cand; > 70 for(int u: g[v]) > 71 if(det_height[u] == 0) > 72 cand.push_back(u); > 73 if(dh==h) > 74 det_parent[v] = -2; > 75 if(cand.size() == 1 && dh<h) { > 76 int u = cand.front(); > 77 Q2.push_back(u); > 78 det_child[u].emplace_back(v); > 79 det_parent[v] = u; > 80 if(det_child[u].size() > 2) > 81 return false; > 82 susp_edges.erase(make_pair(min(v > 83 } > 84 } else { > 85 return false; > 86 } > 87 } > 88 Q.swap(Q2); > 89 } > 90 > 91 queue<int> QQ; > 92 for(int v=0; v<N; ++v) > 93 QQ.push(v); > 94 while(!QQ.empty()){ > 95 int v = QQ.front(); QQ.pop(); > 96 if(det_height[v]==0 || det_parent[v]!=-1) > 97 continue; > 98 > 99 vector<int> cand; > 100 for(int u: g[v]) > 101 if(det_height[u] == det_height[v]+1 || det_heigh > 102 cand.push_back(u); > 103 if(cand.size() == 1) { > 104 int u = cand.front(); > 105 QQ.push(u); > 106 det_child[u].emplace_back(v); > 107 det_parent[v] = u; > 108 if(det_child[u].size() > 2) > 109 return false; > 110 susp_edges.erase(make_pair(min(v,u), max(v,u))); > 111 } > 112 } > 113 > 114 int cnt = 0; > 115 for(int dh: det_height) > 116 if(dh) > 117 ++cnt; > 118 cerr << cnt << " / " << N << " @ " << susp_edges.size() << endl; > 119 return susp_edges.size() == added; > 120 } > 121 }; > 122 > 123 // BEGIN CUT HERE > 124 #include <ctime> > 125 double start_time; string timer() > 126 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 127 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 128 { os << "{ "; > 129 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 130 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 131 void verify_case(const string& Expected, const string& Received) { > 132 bool ok = (Expected == Received); > 133 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 134 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 135 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 136 #define END verify_case(_, TheKingsRoadsDiv1().getAnswer(h, a, b));} > 137 int main(){ > 138 > 139 CASE(0) > 140 int h = 3; > 141 int a_[] = {1, 3, 2, 2, 3, 7, 1, 5, 4}; > 142 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 143 int b_[] = {6, 5, 4, 7, 4, 3, 3, 1, 7}; > 144 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 145 string _ = "Correct"; > 146 END > 147 CASE(1) > 148 int h = 2; > 149 int a_[] = {1, 2, 1, 3, 3}; > 150 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 151 int b_[] = {2, 1, 2, 3, 3}; > 152 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 153 string _ = "Incorrect"; > 154 END > 155 CASE(2) > 156 int h = 3; > 157 int a_[] = {1, 3, 2, 2, 6, 6, 4, 4, 7}; > 158 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 159 int b_[] = {2, 1, 4, 5, 4, 4, 7, 7, 6}; > 160 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 161 string _ = "Incorrect"; > 162 END > 163 CASE(3) > 164 int h = 2; > 165 int a_[] = {1, 2, 2, 1, 1}; > 166 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 167 int b_[] = {1, 2, 2, 1, 2}; > 168 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 169 string _ = "Incorrect"; > 170 END > 171 CASE(4) > 172 int h = 5; > 173 int a_[] = {6, 15, 29, 28, 7, 13, 13, 23, 28, 13, 30, 27, 14, 4, 14, 19, > 174 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 175 int b_[] = {9, 22, 30, 20, 26, 25, 8, 7, 24, 21, 27, 31, 4, 28, 29, 6, 1 > 176 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 177 string _ = "Correct"; > 178 END > 179 CASE(5) > 180 int h = 2; > 181 int a_[] = {1,1,1,2,1}; > 182 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 183 int b_[] = {2,3,1,2,2}; > 184 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 185 string _ = "Correct"; > 186 END > 187 /* > 188 CASE(6) > 189 int h = ; > 190 int a_[] = ; > 191 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 192 int b_[] = ; > 193 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 194 string _ = ; > 195 END > 196 CASE(7) > 197 int h = ; > 198 int a_[] = ; > 199 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 200 int b_[] = ; > 201 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 202 string _ = ; > 203 END > 204 */ > 205 } > 206 // END CUT HERE