ea99443fa2 2014-06-07 kinaba: #include <iostream> ea99443fa2 2014-06-07 kinaba: #include <sstream> ea99443fa2 2014-06-07 kinaba: #include <iomanip> ea99443fa2 2014-06-07 kinaba: #include <vector> ea99443fa2 2014-06-07 kinaba: #include <string> ea99443fa2 2014-06-07 kinaba: #include <map> ea99443fa2 2014-06-07 kinaba: #include <set> ea99443fa2 2014-06-07 kinaba: #include <algorithm> ea99443fa2 2014-06-07 kinaba: #include <numeric> ea99443fa2 2014-06-07 kinaba: #include <iterator> ea99443fa2 2014-06-07 kinaba: #include <functional> ea99443fa2 2014-06-07 kinaba: #include <complex> ea99443fa2 2014-06-07 kinaba: #include <queue> ea99443fa2 2014-06-07 kinaba: #include <stack> ea99443fa2 2014-06-07 kinaba: #include <cmath> ea99443fa2 2014-06-07 kinaba: #include <cassert> ea99443fa2 2014-06-07 kinaba: #include <tuple> ea99443fa2 2014-06-07 kinaba: using namespace std; ea99443fa2 2014-06-07 kinaba: typedef long long LL; ea99443fa2 2014-06-07 kinaba: typedef complex<double> CMP; ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: class CatchTheBeat { public: ea99443fa2 2014-06-07 kinaba: int maxCatched(int n, int x0, int y0, int a, int b, int c, int d, int mod1, int mod2, int offset) ea99443fa2 2014-06-07 kinaba: { ea99443fa2 2014-06-07 kinaba: vector<int> x(n), y(n); ea99443fa2 2014-06-07 kinaba: x[0] = x0; ea99443fa2 2014-06-07 kinaba: for(int i=1; i<n; ++i) ea99443fa2 2014-06-07 kinaba: x[i] = int((LL(x[i-1]) * a + b) % mod1); ea99443fa2 2014-06-07 kinaba: for(int i=0; i<n; ++i) ea99443fa2 2014-06-07 kinaba: x[i] = x[i] - offset; ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: y[0] = y0; ea99443fa2 2014-06-07 kinaba: for(int i=1; i<n; ++i) ea99443fa2 2014-06-07 kinaba: y[i] = int((LL(y[i-1]) * c + d) % mod2); ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: return solve(n, x, y); ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: int solve(int N, const vector<int>& x, const vector<int>& y) ea99443fa2 2014-06-07 kinaba: { ea99443fa2 2014-06-07 kinaba: vector<pair<int,int>> tx; ea99443fa2 2014-06-07 kinaba: for(int i=0; i<N; ++i) ea99443fa2 2014-06-07 kinaba: tx.emplace_back(y[i], x[i]); ea99443fa2 2014-06-07 kinaba: tx.emplace_back(0, 0); ea99443fa2 2014-06-07 kinaba: sort(tx.begin(), tx.end()); ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: vector<vector<int>> score_table(tx.size()); ea99443fa2 2014-06-07 kinaba: score_table[0].push_back(0); ea99443fa2 2014-06-07 kinaba: int best_score = 0; ea99443fa2 2014-06-07 kinaba: for(int c=1; c<tx.size(); ++c) ea99443fa2 2014-06-07 kinaba: { ea99443fa2 2014-06-07 kinaba: int pre = -1; ea99443fa2 2014-06-07 kinaba: for(int bs=best_score; bs>=0; --bs) { ea99443fa2 2014-06-07 kinaba: for(int p: score_table[bs]) ea99443fa2 2014-06-07 kinaba: if(tx[c].first - tx[p].first >= abs(tx[c].second - tx[p].second)) ea99443fa2 2014-06-07 kinaba: {pre = bs; goto found_pre;} ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: found_pre: ea99443fa2 2014-06-07 kinaba: if(pre>=0) { ea99443fa2 2014-06-07 kinaba: score_table[pre+1].push_back(c); ea99443fa2 2014-06-07 kinaba: best_score = max(best_score, pre+1); ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: return best_score; ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: }; ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: // BEGIN CUT HERE ea99443fa2 2014-06-07 kinaba: #include <ctime> ea99443fa2 2014-06-07 kinaba: double start_time; string timer() ea99443fa2 2014-06-07 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } ea99443fa2 2014-06-07 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) ea99443fa2 2014-06-07 kinaba: { os << "{ "; ea99443fa2 2014-06-07 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) ea99443fa2 2014-06-07 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } ea99443fa2 2014-06-07 kinaba: void verify_case(const int& Expected, const int& Received) { ea99443fa2 2014-06-07 kinaba: bool ok = (Expected == Received); ea99443fa2 2014-06-07 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; ea99443fa2 2014-06-07 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } ea99443fa2 2014-06-07 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); ea99443fa2 2014-06-07 kinaba: #define END verify_case(_, CatchTheBeat().maxCatched(n, x0, y0, a, b, c, d, mod1, mod2, offset));} ea99443fa2 2014-06-07 kinaba: int main(){ ea99443fa2 2014-06-07 kinaba: ea99443fa2 2014-06-07 kinaba: CASE(0) ea99443fa2 2014-06-07 kinaba: int n = 3; ea99443fa2 2014-06-07 kinaba: int x0 = 0; ea99443fa2 2014-06-07 kinaba: int y0 = 0; ea99443fa2 2014-06-07 kinaba: int a = 1; ea99443fa2 2014-06-07 kinaba: int b = 1; ea99443fa2 2014-06-07 kinaba: int c = 1; ea99443fa2 2014-06-07 kinaba: int d = 1; ea99443fa2 2014-06-07 kinaba: int mod1 = 100; ea99443fa2 2014-06-07 kinaba: int mod2 = 100; ea99443fa2 2014-06-07 kinaba: int offset = 1; ea99443fa2 2014-06-07 kinaba: int _ = 2; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: CASE(1) ea99443fa2 2014-06-07 kinaba: int n = 1; ea99443fa2 2014-06-07 kinaba: int x0 = 0; ea99443fa2 2014-06-07 kinaba: int y0 = 1234; ea99443fa2 2014-06-07 kinaba: int a = 0; ea99443fa2 2014-06-07 kinaba: int b = 0; ea99443fa2 2014-06-07 kinaba: int c = 0; ea99443fa2 2014-06-07 kinaba: int d = 0; ea99443fa2 2014-06-07 kinaba: int mod1 = 1000000000; ea99443fa2 2014-06-07 kinaba: int mod2 = 1000000000; ea99443fa2 2014-06-07 kinaba: int offset = 1000; ea99443fa2 2014-06-07 kinaba: int _ = 1; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: CASE(2) ea99443fa2 2014-06-07 kinaba: int n = 1; ea99443fa2 2014-06-07 kinaba: int x0 = 0; ea99443fa2 2014-06-07 kinaba: int y0 = 999; ea99443fa2 2014-06-07 kinaba: int a = 0; ea99443fa2 2014-06-07 kinaba: int b = 0; ea99443fa2 2014-06-07 kinaba: int c = 0; ea99443fa2 2014-06-07 kinaba: int d = 0; ea99443fa2 2014-06-07 kinaba: int mod1 = 1000000000; ea99443fa2 2014-06-07 kinaba: int mod2 = 1000000000; ea99443fa2 2014-06-07 kinaba: int offset = 1000; ea99443fa2 2014-06-07 kinaba: int _ = 0; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: CASE(3) ea99443fa2 2014-06-07 kinaba: int n = 100; ea99443fa2 2014-06-07 kinaba: int x0 = 0; ea99443fa2 2014-06-07 kinaba: int y0 = 0; ea99443fa2 2014-06-07 kinaba: int a = 1; ea99443fa2 2014-06-07 kinaba: int b = 1; ea99443fa2 2014-06-07 kinaba: int c = 1; ea99443fa2 2014-06-07 kinaba: int d = 1; ea99443fa2 2014-06-07 kinaba: int mod1 = 3; ea99443fa2 2014-06-07 kinaba: int mod2 = 58585858; ea99443fa2 2014-06-07 kinaba: int offset = 1; ea99443fa2 2014-06-07 kinaba: int _ = 66; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: CASE(4) ea99443fa2 2014-06-07 kinaba: int n = 500000; ea99443fa2 2014-06-07 kinaba: int x0 = 123456; ea99443fa2 2014-06-07 kinaba: int y0 = 0; ea99443fa2 2014-06-07 kinaba: int a = 1; ea99443fa2 2014-06-07 kinaba: int b = 0; ea99443fa2 2014-06-07 kinaba: int c = 1; ea99443fa2 2014-06-07 kinaba: int d = 1; ea99443fa2 2014-06-07 kinaba: int mod1 = 1000000000; ea99443fa2 2014-06-07 kinaba: int mod2 = 1000000000; ea99443fa2 2014-06-07 kinaba: int offset = 0; ea99443fa2 2014-06-07 kinaba: int _ = 376544; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: CASE(5) ea99443fa2 2014-06-07 kinaba: int n = 500000; ea99443fa2 2014-06-07 kinaba: int x0 = 0; ea99443fa2 2014-06-07 kinaba: int y0 = 0; ea99443fa2 2014-06-07 kinaba: int a = 0; ea99443fa2 2014-06-07 kinaba: int b = 0; ea99443fa2 2014-06-07 kinaba: int c = 0; ea99443fa2 2014-06-07 kinaba: int d = 0; ea99443fa2 2014-06-07 kinaba: int mod1 = 1; ea99443fa2 2014-06-07 kinaba: int mod2 = 1; ea99443fa2 2014-06-07 kinaba: int offset = 0; ea99443fa2 2014-06-07 kinaba: int _ = 500000; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: CASE(6) ea99443fa2 2014-06-07 kinaba: int n = 10; ea99443fa2 2014-06-07 kinaba: int x0 = 999999957; ea99443fa2 2014-06-07 kinaba: int y0 = 79; ea99443fa2 2014-06-07 kinaba: int a = 993948167; ea99443fa2 2014-06-07 kinaba: int b = 24597383; ea99443fa2 2014-06-07 kinaba: int c = 212151897; ea99443fa2 2014-06-07 kinaba: int d = 999940854; ea99443fa2 2014-06-07 kinaba: int mod1 = 999999986; ea99443fa2 2014-06-07 kinaba: int mod2 = 999940855; ea99443fa2 2014-06-07 kinaba: int offset = 3404; ea99443fa2 2014-06-07 kinaba: int _ = 3; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: /* ea99443fa2 2014-06-07 kinaba: CASE(7) ea99443fa2 2014-06-07 kinaba: int n = ; ea99443fa2 2014-06-07 kinaba: int x0 = ; ea99443fa2 2014-06-07 kinaba: int y0 = ; ea99443fa2 2014-06-07 kinaba: int a = ; ea99443fa2 2014-06-07 kinaba: int b = ; ea99443fa2 2014-06-07 kinaba: int c = ; ea99443fa2 2014-06-07 kinaba: int d = ; ea99443fa2 2014-06-07 kinaba: int mod1 = ; ea99443fa2 2014-06-07 kinaba: int mod2 = ; ea99443fa2 2014-06-07 kinaba: int offset = ; ea99443fa2 2014-06-07 kinaba: int _ = ; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: CASE(8) ea99443fa2 2014-06-07 kinaba: int n = ; ea99443fa2 2014-06-07 kinaba: int x0 = ; ea99443fa2 2014-06-07 kinaba: int y0 = ; ea99443fa2 2014-06-07 kinaba: int a = ; ea99443fa2 2014-06-07 kinaba: int b = ; ea99443fa2 2014-06-07 kinaba: int c = ; ea99443fa2 2014-06-07 kinaba: int d = ; ea99443fa2 2014-06-07 kinaba: int mod1 = ; ea99443fa2 2014-06-07 kinaba: int mod2 = ; ea99443fa2 2014-06-07 kinaba: int offset = ; ea99443fa2 2014-06-07 kinaba: int _ = ; ea99443fa2 2014-06-07 kinaba: END ea99443fa2 2014-06-07 kinaba: */ ea99443fa2 2014-06-07 kinaba: } ea99443fa2 2014-06-07 kinaba: // END CUT HERE