ADDED SRM/538-U/1A.cpp
Index: SRM/538-U/1A.cpp
==================================================================
--- SRM/538-U/1A.cpp
+++ SRM/538-U/1A.cpp
@@ -0,0 +1,123 @@
+#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>
+using namespace std;
+typedef long long LL;
+typedef long double LD;
+typedef complex<LD> CMP;
+
+class EvenRoute { public:
+ string isItPossible(vector <int> x, vector <int> y, int wantedParity)
+ {
+ bool can = false;
+ for(int i=0; i<x.size(); ++i)
+ if( ((x[i]+y[i])&1) == wantedParity )
+ can = true;
+ return can ? "CAN" : "CANNOT";
+ }
+};
+
+// 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(_, EvenRoute().isItPossible(x, y, wantedParity));}
+int main(){
+
+CASE(0)
+ int x_[] = {-1,-1,1,1};
+ vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
+ int y_[] = {-1,1,1,-1};
+ vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
+ int wantedParity = 0;
+ string _ = "CAN";
+END
+CASE(1)
+ int x_[] = {-5,-3,2};
+ vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
+ int y_[] = {2,0,3};
+ vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
+ int wantedParity = 1;
+ string _ = "CAN";
+END
+CASE(2)
+ int x_[] = {1001, -4000};
+ vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
+ int y_[] = {0,0};
+ vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
+ int wantedParity = 1;
+ string _ = "CAN";
+END
+CASE(3)
+ int x_[] = {11, 21, 0};
+ vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
+ int y_[] = {-20, 42, 7};
+ vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
+ int wantedParity = 0;
+ string _ = "CANNOT";
+END
+CASE(4)
+ int x_[] = {0, 6};
+ vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
+ int y_[] = {10, -20};
+ vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
+ int wantedParity = 1;
+ string _ = "CANNOT";
+END
+CASE(5)
+ int x_[] = {159833,-62665,323889,-235879,137089,-669850,137554,549764,191807,993220,-801864,-425902,326896,312318,-778686,33030,763633,-866343,36938,-627234,-19941,-909928,-920678,-763769,657773,431660,600784,54912,563394,970744,872933,-413697,319375,249696,368559,-449659,942650,997004,-420096,-473219,-757172,70934,-771310,498140,-870998,176429,985061,-674033,255167,-89503};
+ vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
+ int y_[] = {38668,957082,-75351,-877610,-247852,458917,-417575,219160,515259,-254435,-441099,631589,-637191,-902042,-662042,-279031,-233412,-443322,207905,-566785,-248122,829715,362587,831403,-238955,792643,77852,665108,83526,-623925,-199287,492427,311357,-437880,39341,988852,-261007,-621546,-659372,-661305,196329,769159,-771255,-888939,483180,-151127,-533736,281297,411246,-339825};
+ vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
+ int wantedParity = 0;
+ string _ = "???";
+END
+CASE(5)
+ int x_[] = {159833,-62665,323889,-235879,137089,-669850,137554,549764,191807,993220,-801864,-425902,326896,312318,-778686,33030,763633,-866343,36938,-627234,-19941,-909928,-920678,-763769,657773,431660,600784,54912,563394,970744,872933,-413697,319375,249696,368559,-449659,942650,997004,-420096,-473219,-757172,70934,-771310,498140,-870998,176429,985061,-674033,255167,-89503};
+ vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
+ int y_[] = {38668,957082,-75351,-877610,-247852,458917,-417575,219160,515259,-254435,-441099,631589,-637191,-902042,-662042,-279031,-233412,-443322,207905,-566785,-248122,829715,362587,831403,-238955,792643,77852,665108,83526,-623925,-199287,492427,311357,-437880,39341,988852,-261007,-621546,-659372,-661305,196329,769159,-771255,-888939,483180,-151127,-533736,281297,411246,-339825};
+ vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
+ int wantedParity = 1;
+ string _ = "???";
+END
+CASE(6)
+ int x_[] = {159833,-62665,323889,-235879,137089,-669850,137554,549764,191807,993220,-801864,-425902,326896,312318,-778686,33030,763633,-866343,36938,-627234,-19941,-909928,-920678,-763769,657773,431660,600784,54912,563394,970744,872933,-413697,319375,249696,368559,-449659,942650,997004,-420096,-473219,-757172,70934,-771310,498140,-870998,176429,985061,-674033,255167,-89503};
+ vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
+ int y_[] = {159833,-62665,323889,-235879,137089,-669850,137554,549764,191807,993220,-801864,-425902,326896,312318,-778686,33030,763633,-866343,36938,-627234,-19941,-909928,-920678,-763769,657773,431660,600784,54912,563394,970744,872933,-413697,319375,249696,368559,-449659,942650,997004,-420096,-473219,-757172,70934,-771310,498140,-870998,176429,985061,-674033,255167,-89503};
+ vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
+ int wantedParity = 0;
+ string _ = "???";
+END
+CASE(6)
+ int x_[] = {159833,-62665,323889,-235879,137089,-669850,137554,549764,191807,993220,-801864,-425902,326896,312318,-778686,33030,763633,-866343,36938,-627234,-19941,-909928,-920678,-763769,657773,431660,600784,54912,563394,970744,872933,-413697,319375,249696,368559,-449659,942650,997004,-420096,-473219,-757172,70934,-771310,498140,-870998,176429,985061,-674033,255167,-89503};
+ vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
+ int y_[] = {159833,-62665,323889,-235879,137089,-669850,137554,549764,191807,993220,-801864,-425902,326896,312318,-778686,33030,763633,-866343,36938,-627234,-19941,-909928,-920678,-763769,657773,431660,600784,54912,563394,970744,872933,-413697,319375,249696,368559,-449659,942650,997004,-420096,-473219,-757172,70934,-771310,498140,-870998,176429,985061,-674033,255167,-89503};
+ vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
+ int wantedParity = 1;
+ string _ = "???";
+END
+
+}
+// END CUT HERE
ADDED SRM/542-U/1A.cpp
Index: SRM/542-U/1A.cpp
==================================================================
--- SRM/542-U/1A.cpp
+++ SRM/542-U/1A.cpp
@@ -0,0 +1,110 @@
+#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>
+using namespace std;
+typedef long long LL;
+typedef long double LD;
+typedef complex<LD> CMP;
+
+class PatrolRoute { public:
+ int countRoutes(int X, int Y, int minT, int maxT)
+ {
+ --X, --Y;
+
+ LL count = 0;
+ for(int W=2; W<=X; ++W)
+ for(int H=2; H<=Y; ++H)
+ if( minT <= (W+H)*2 && (W+H)*2 <= maxT )
+ count = (count + threePoints(W,H) * (X-W+1)*(Y-H+1)) % 1000000007;
+ return count;
+ }
+
+ LL threePoints(int W, int H)
+ {
+ LL a = (W-1)*(H-1);
+ LL b = (W-1)*(H-1);
+ return 4*a + 2*b;
+ }
+};
+
+// 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 int& Expected, const int& 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(_, PatrolRoute().countRoutes(X, Y, minT, maxT));}
+int main(){
+
+CASE(0)
+ int X = 3;
+ int Y = 3;
+ int minT = 1;
+ int maxT = 20000;
+ int _ = 6;
+END
+CASE(1)
+ int X = 3;
+ int Y = 3;
+ int minT = 4;
+ int maxT = 7;
+ int _ = 0;
+END
+CASE(2)
+ int X = 4;
+ int Y = 6;
+ int minT = 9;
+ int maxT = 12;
+ int _ = 264;
+END
+CASE(3)
+ int X = 7;
+ int Y = 5;
+ int minT = 13;
+ int maxT = 18;
+ int _ = 1212;
+END
+CASE(4)
+ int X = 4000;
+ int Y = 4000;
+ int minT = 4000;
+ int maxT = 14000;
+ int _ = 859690013;
+END
+CASE(5)
+ int X = 4000;
+ int Y = 4000;
+ int minT = 1;
+ int maxT = 20000;
+ int _ = -1;
+END
+CASE(6)
+ int X = 3;
+ int Y = 3;
+ int minT = 1;
+ int maxT = 1;
+ int _ = 0;
+END
+
+}
+// END CUT HERE
ADDED SRM/545-U/1A.cpp
Index: SRM/545-U/1A.cpp
==================================================================
--- SRM/545-U/1A.cpp
+++ SRM/545-U/1A.cpp
@@ -0,0 +1,130 @@
+#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>
+using namespace std;
+typedef long long LL;
+typedef long double LD;
+typedef complex<LD> CMP;
+
+class StrIIRec { public:
+ string recovstr(int n, int minInv, string minStr)
+ {
+ for(int i=0; i<n; ++i)
+ if(minStr.find(char('a'+i)) == string::npos)
+ minStr += char('a'+i);
+
+ for(int i=n-1; i>=0; --i) {
+ string pre = minStr.substr(0,i);
+ string post = minStr.substr(i);
+ sort(post.rbegin(), post.rend());
+ if( inv(pre+post) >= minInv )
+ if(i==n-1) {
+ return pre+post;
+ } else {
+ string mid = "";
+ for(int m=i; m<n; ++m)
+ {
+ for(int k=post.size()-1; k>=0; --k)
+ if((m==i && post[k]>minStr[i]) || (m!=i)) {
+ string mmid = mid + post[k];
+ string ppost = post.substr(0,k) + post.substr(k+1);
+ if( inv(pre+mmid+ppost) >= minInv ) {
+ mid = mmid;
+ post = ppost;
+ goto nextM;
+ }
+ }
+ nextM:;
+ }
+ return pre + mid;
+ }
+ }
+ return "???";
+ }
+
+ int inv(const string& s)
+ {
+ int cnt = 0;
+ for(int i=0; i<s.size(); ++i)
+ for(int j=i+1; j<s.size(); ++j)
+ if(s[i]>s[j])
+ ++cnt;
+ return cnt;
+ }
+};
+
+// 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(_, StrIIRec().recovstr(n, minInv, minStr));}
+int main(){
+
+CASE(0)
+ int n = 2;
+ int minInv = 1;
+ string minStr = "ab";
+ string _ = "ba";
+END
+CASE(1)
+ int n = 9;
+ int minInv = 1;
+ string minStr = "efcdgab";
+ string _ = "efcdgabhi";
+END
+CASE(2)
+ int n = 11;
+ int minInv = 55;
+ string minStr = "debgikjfc";
+ string _ = "kjihgfedcba";
+END
+CASE(3)
+ int n = 15;
+ int minInv = 0;
+ string minStr = "e";
+ string _ = "eabcdfghijklmno";
+END
+CASE(4)
+ int n = 9;
+ int minInv = 20;
+ string minStr = "fcdebiha";
+ string _ = "fcdehigba";
+END
+CASE(5)
+ int n = 20;
+ int minInv = 100;
+ string minStr = "abcdefghijklmnopqrst";
+ string _ = "?";
+END
+/*
+CASE(6)
+ int n = ;
+ int minInv = ;
+ string minStr = ;
+ string _ = ;
+END
+*/
+}
+// END CUT HERE
ADDED SRM/545-U/1B.cpp
Index: SRM/545-U/1B.cpp
==================================================================
--- SRM/545-U/1B.cpp
+++ SRM/545-U/1B.cpp
@@ -0,0 +1,150 @@
+#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>
+using namespace std;
+typedef long long LL;
+typedef long double LD;
+typedef complex<LD> CMP;
+
+static const int MODVAL = 1000000007;
+struct mint
+{
+ int val;
+ mint():val(0){}
+ mint(int x):val(x%MODVAL) {}
+ mint(size_t x):val(x%MODVAL) {}
+ mint(LL x):val(x%MODVAL) {}
+};
+mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
+mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
+mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
+mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
+mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); }
+mint operator+(mint x, mint y) { return x+=y; }
+mint operator-(mint x, mint y) { return x-=y; }
+mint operator*(mint x, mint y) { return x*=y; }
+mint operator/(mint x, mint y) { return x/=y; }
+vector<mint> FAC_(1,1);
+mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); return FAC_[n]; }
+//mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); }
+
+vector< vector<mint> > CP_;
+mint C(LL n, LL k) {
+ while( CP_.size() <= n ) {
+ int nn = CP_.size();
+ CP_.push_back(vector<mint>(nn+1,1));
+ for(int kk=1; kk<nn; ++kk)
+ CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk];
+ }
+ return k<0 || n<k ? 0 : CP_[n][k];
+}
+
+int gcd(int a, int b) {
+ while(a)
+ swap(a, b%=a);
+ return b;
+}
+
+class Spacetsk { public:
+ int countsets(int L, int H, int K)
+ {
+ if( K==1 )
+ return (L+1)*(H+1);
+
+ mint sum = 0;
+ for(int x=0; x<=L; ++x)
+ for(int y=1; y<=H; ++y)
+ {
+ mint dup = (x==0 ? L+1 : 2*(L+1-x));
+ mint mid = C(gcd(x, y), K-1);
+ sum = sum + dup*mid;
+ }
+ return sum.val;
+ }
+};
+
+// 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 int& Expected, const int& 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(_, Spacetsk().countsets(L, H, K));}
+int main(){
+
+CASE(0)
+ int L = 1;
+ int H = 1;
+ int K = 2;
+ int _ = 4;
+END
+CASE(1)
+ int L = 1;
+ int H = 1;
+ int K = 1;
+ int _ = 4;
+END
+CASE(2)
+ int L = 2;
+ int H = 2;
+ int K = 1;
+ int _ = 9;
+END
+CASE(3)
+ int L = 2;
+ int H = 2;
+ int K = 2;
+ int _ = 23;
+END
+CASE(4)
+ int L = 5;
+ int H = 5;
+ int K = 3;
+ int _ = 202;
+END
+CASE(5)
+ int L = 561;
+ int H = 394;
+ int K = 20;
+ int _ = 786097180;
+END
+CASE(6)
+ int L = 1;
+ int H = 1;
+ int K = 1;
+ int _ = 4;
+END
+CASE(7)
+ int L = 2000;
+ int H = 2000;
+ int K = 500;
+ int _ = -1;
+END
+CASE(7)
+ int L = 2000;
+ int H = 2000;
+ int K = 2;
+ int _ = -1;
+END
+}
+// END CUT HERE