ADDED SRM/680-U/1A.cpp
Index: SRM/680-U/1A.cpp
==================================================================
--- SRM/680-U/1A.cpp
+++ SRM/680-U/1A.cpp
@@ -0,0 +1,158 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+#include <tuple>
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+class BearFair { public:
+ string isFair(int n, int b, vector <int> upTo, vector <int> quantity)
+ {
+ return isFair_bool(n, b, upTo, quantity) ? "fair" : "unfair";
+ }
+
+ bool isFair_bool(int n, int b, vector <int> upTo, vector <int> quantity)
+ {
+ set<pair<int,int>> uqs;
+ for(int i=0; i<upTo.size(); ++i)
+ uqs.emplace(upTo[i], quantity[i]);
+ uqs.emplace(b, n);
+ vector<pair<int,int>> uq(uqs.begin(), uqs.end());
+
+ int LastU=0, LastQ=0;
+ set<pair<int,int>> Cand;
+ Cand.emplace(0, 0);
+
+ for(auto& uqi: uq) {
+ int u = uqi.first;
+ int q = uqi.second;
+ if(LastQ>q || (u==LastU && q!=LastQ))
+ return false;
+
+ int Do = (u-LastU)/2 + ((u-LastU)%2==1 && u%2==1 ? 1 : 0);
+ int De = (u-LastU)/2 + ((u-LastU)%2==1 && u%2==0 ? 1 : 0);
+ int Dq = q - LastQ;
+ if(Dq > Do+De)
+ return false;
+
+ LastU=u, LastQ=q;
+ if(Dq == 0)
+ continue;
+
+ set<pair<int,int>> neo;
+ for(auto c: Cand) {
+ int o = c.first;
+ int e = c.second;
+
+ for(int oo=0; oo<=Do && oo<=Dq; ++oo) {
+ int ee = Dq - oo;
+ if(0<=ee && ee<=De && o+oo<=n/2 && e+ee<=n/2) {
+ neo.emplace(o+oo, e+ee);
+ }
+ }
+ }
+ Cand = std::move(neo);
+ }
+
+ return Cand.count(make_pair(n/2, n/2)) > 0;
+ }
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+ for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+ os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const string& Expected, const string& Received) {
+ bool ok = (Expected == Received);
+ if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END verify_case(_, BearFair().isFair(n, b, upTo, quantity));}
+int main(){
+
+CASE(0)
+ int n = 4;
+ int b = 6;
+ int upTo_[] = {3,6};
+ vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_));
+ int quantity_[] = {2,4};
+ vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_));
+ string _ = "fair";
+END
+CASE(1)
+ int n = 4;
+ int b = 6;
+ int upTo_[] = {3,6};
+ vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_));
+ int quantity_[] = {2,3};
+ vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_));
+ string _ = "unfair";
+END
+CASE(2)
+ int n = 2;
+ int b = 6;
+ int upTo_[] = {1,2,3};
+ vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_));
+ int quantity_[] = {1,1,2};
+ vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_));
+ string _ = "unfair";
+END
+CASE(3)
+ int n = 50;
+ int b = 1000;
+ int upTo_[] = {736,205,264,235,273,40,901,37,900,424,122,517,820,402,669,279,455,921,774,923,107,936,484,171,248,
+186,970,231,321,902,606,24,451,585,823,270,361,292,128,521,689,683,270,726,980,652,996,909,196,357};
+ vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_));
+ int quantity_[] = {35,9,9,9,9,3,46,3,46,18,7,25,39,18,32,9,20,49,37,49,7,49,24,8,9,8,49,9,12,46,29,2,20,29,39,9,16,11,7,27,33,32,9,34,49,32,50,47,8,16};
+ vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_));
+ string _ = "fair";
+END
+CASE(4)
+ int n = 4;
+ int b = 1000;
+ int upTo_[] = {400,600};
+ vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_));
+ int quantity_[] = {4,0};
+ vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_));
+ string _ = "unfair";
+END
+/*
+CASE(5)
+ int n = ;
+ int b = ;
+ int upTo_[] = ;
+ vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_));
+ int quantity_[] = ;
+ vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_));
+ string _ = ;
+END
+CASE(6)
+ int n = ;
+ int b = ;
+ int upTo_[] = ;
+ vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_));
+ int quantity_[] = ;
+ vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_));
+ string _ = ;
+END
+*/
+}
+// END CUT HERE
ADDED SRM/680-U/1B.cpp
Index: SRM/680-U/1B.cpp
==================================================================
--- SRM/680-U/1B.cpp
+++ SRM/680-U/1B.cpp
@@ -0,0 +1,224 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+#include <tuple>
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+class BearSpans { public:
+ vector <int> findAnyGraph(int n, int m, int k)
+ {
+ if(k>29 || (1<<k)>n)
+ return vector<int>(1, -1);
+
+ // generate basic
+ vector<int> ans = gen_base(1, 1<<k);
+ for(int p=1, v=(1<<k)+1; v<=n; p=v++) {
+ ans.push_back(p);
+ ans.push_back(v);
+ }
+
+ vector<vector<bool>> used(n+1, vector<bool>(n+1));
+ for(int i=0; i<ans.size(); i+=2) {
+ used[ans[i]][ans[i+1]] = true;
+ used[ans[i+1]][ans[i]] = true;
+ }
+
+ for(int s=1; s<=n && ans.size()<2*m; ++s)
+ for(int e=s+1; e<=n && ans.size()<2*m; ++e)
+ if(!used[s][e]) {
+ ans.push_back(s);
+ ans.push_back(e);
+ }
+
+ return ans;
+ }
+
+ vector<int> gen_base(int vS, int vE)
+ {
+ if(vS+1 == vE) {
+ vector<int> ans;
+ ans.push_back(vS);
+ ans.push_back(vE);
+ return ans;
+ }
+
+ int vM1 = vS + (vE-vS+1)/2 -1;
+ int vM2 = vS + (vE-vS+1)/2;
+ vector<int> a = gen_base(vS, vM1);
+ vector<int> b = gen_base(vM2, vE);
+ a.insert(a.end(), b.begin(), b.end());
+ a.push_back(vM1);
+ a.push_back(vM2);
+ return a;
+ }
+};
+
+// BEGIN CUT HERE
+struct UnionFind
+{
+ vector<int> uf, sz;
+ int nc;
+
+ UnionFind(int N): uf(N), sz(N,1), nc(N)
+ { for(int i=0; i<N; ++i) uf[i] = i; }
+ int size()
+ { return nc; }
+ int size(int a)
+ { return sz[Find(a)]; }
+ int Find(int a)
+ { return uf[a]==a ? a : uf[a]=Find(uf[a]); }
+ // Semi-compression w.o. recursion.
+ //{ while(uf[a] != a) a=uf[a]=uf[uf[a]]; return a; }
+ bool Union(int a, int b)
+ {
+ a = Find(a);
+ b = Find(b);
+ if( a != b )
+ {
+ if( sz[a] >= sz[b] ) swap(a, b);
+ uf[a] = b;
+ sz[b] += sz[a];
+ --nc;
+ }
+ return (a!=b);
+ }
+};
+
+int verify(vector<int> ans)
+{
+ int m = ans.size() / 2;
+ int n = *max_element(ans.begin(), ans.end());
+ if(n == -1)
+ return -1;
+ vector<tuple<int,int,int>> cft;
+ for(int i=0; i<m; ++i)
+ cft.emplace_back(i+1, ans[2*i+0]-1, ans[2*i+1]-1);
+ vector<bool> added(cft.size());
+
+ UnionFind uf(n);
+ int LoopCount=0;
+ while(uf.size() > 1) {
+ vector<int> to_add;
+ vector<bool> done(n);
+
+ for(int e=0; e<cft.size(); ++e) if(!added[e]) {
+ int a = uf.Find(get<1>(cft[e]));
+ int b = uf.Find(get<2>(cft[e]));
+ if(a!=b) {
+ if(!done[a] || !done[b]) {
+ to_add.push_back(e);
+ done[a] = true;
+ done[b] = true;
+ }
+ }
+ }
+
+ for(int e: to_add) {
+ added[e] = true;
+ uf.Union(get<1>(cft[e]), get<2>(cft[e]));
+ }
+
+ LoopCount++;
+ }
+ return LoopCount;
+}
+
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+ for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+ os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const vector <int>& Expected, const vector <int>& Received) {
+
+ bool ok = (verify(Expected) == verify(Received));
+ if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END verify_case(_, BearSpans().findAnyGraph(n, m, k));}
+int main(){
+
+CASE(0)
+ int n = 17;
+ int m = 22;
+ int k = 1;
+ int __[] = {1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 1, 11, 1, 12, 1, 13, 1, 14, 1, 15, 1, 16, 1, 17, 2, 3, 2, 8, 3, 9, 8, 9, 10, 12, 12, 14 };
+ vector <int> _(__, __+sizeof(__)/sizeof(*__));
+END
+CASE(1)
+ int n = 9;
+ int m = 12;
+ int k = 3;
+ int __[] = {6, 5, 7, 6, 1, 2, 3, 4, 8, 9, 3, 5, 7, 4, 1, 9, 6, 2, 6, 1, 1, 8, 4, 5 };
+ vector <int> _(__, __+sizeof(__)/sizeof(*__));
+END
+CASE(2)
+ int n = 9;
+ int m = 12;
+ int k = 7;
+ int __[] = {-1 };
+ vector <int> _(__, __+sizeof(__)/sizeof(*__));
+END
+CASE(3)
+ int n = 1000;
+ int m = 999;
+ int k = 970;
+ int __[] = {-1 };
+ vector <int> _(__, __+sizeof(__)/sizeof(*__));
+END
+CASE(4)
+ int n = 2;
+ int m = 1;
+ int k = 1;
+ int __[] = {1, 2 };
+ vector <int> _(__, __+sizeof(__)/sizeof(*__));
+END
+CASE(5)
+ int n = 3;
+ int m = 2;
+ int k = 1;
+ int __[] = {1, 2, 1, 3 };
+ vector <int> _(__, __+sizeof(__)/sizeof(*__));
+END
+CASE(6)
+ int n = 3;
+ int m = 3;
+ int k = 2;
+ int __[] = {-1 };
+ vector <int> _(__, __+sizeof(__)/sizeof(*__));
+END
+/*
+CASE(7)
+ int n = ;
+ int m = ;
+ int k = ;
+ int __[] = ;
+ vector <int> _(__, __+sizeof(__)/sizeof(*__));
+END
+CASE(8)
+ int n = ;
+ int m = ;
+ int k = ;
+ int __[] = ;
+ vector <int> _(__, __+sizeof(__)/sizeof(*__));
+END
+*/
+
+}
+// END CUT HERE