fork download
copy 
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <deque>
  6. #include <queue>
  7. #include <stack>
  8. #include <bitset>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cmath>
  18. #include <cstdlib>
  19. #include <cctype>
  20. #include <string>
  21. #include <cstring>
  22. #include <cstdio>
  23. #include <cmath>
  24. #include <cstdlib>
  25. #include <ctime>
  26. #include <string.h>
  27. #include <fstream>
  28. #include <cassert>
  29. using namespace std;
  30.  
  31. #define sz(a) int((a).size())
  32. #define rep(i, s, n)  for(int i = s; i <= (n); ++i)
  33. #define rev(i, n, s)  for(int i = (n); i >= s; --i)
  34. #define fore(x, a) for(auto &&x : a)
  35. typedef long long ll;
  36. const int mod = 1000000007;
  37. const int N = 100005;
  38.  
  39. int arr[N], k , m, l[N], r[N];
  40. pair<int, int> ab[N], ba[N];
  41.  
  42. bool all_bad(int s, int e) {
  43.   if (e - s + 1 < m) return 1;
  44.   for (int i = s, j = e; i <= e && j >= s && i <= j; i++, j--) {
  45.     if (l[i]<s && r[i]>e) return all_bad(s, i - 1) && all_bad(i + 1, e);
  46.     if (l[j]<s && r[j]>e) return all_bad(s, j - 1) && all_bad(j + 1, e);
  47.   }
  48.   return 0;
  49. }
  50.  
  51. bool cmp(pair<int, int> o1, pair<int, int> o2) {
  52.   if (o1.first != o2.first) return o1.first < o2.first;
  53.   return o1.second > o2.second;
  54. }
  55. set<int> c1, c2;
  56.  
  57. class FindingFriends {
  58. public:
  59.   int shortestDistance( int n, vector <int> init, int a, int b, int c, int d, int m2 ) {
  60.     m = m2;
  61.     int mx = -1, mn = mod;
  62.     rep(i, 0, sz(init) - 1) {
  63.       arr[i] = init[i];
  64.     }
  65.     rep(i, sz(init), n - 1) {
  66.       arr[i] = (arr[i - 1] * 1LL * a + b * 1LL * i + c) % d;
  67.     }
  68.     rep(i, 0, n - 1) {
  69.       mn = min(mn, arr[i]);
  70.       mx = max(mx, arr[i]);
  71.       ab[i] = make_pair(arr[i], i);
  72.       ba[i] = make_pair(arr[i], i);
  73.     }
  74.     sort(ab, ab + n);
  75.     sort(ba, ba + n, cmp);
  76.     int hi = mx - mn, lo = 0;
  77.     while (lo < hi) {
  78.       k = (hi + lo) / 2;
  79.       rep(i, 0, n - 1) {
  80.         l[i] = -1, r[i] = n;
  81.       }
  82.       c1.clear(); c2.clear(); c1.insert(-1); c2.insert(n);
  83.       int j1 = 0, j2 = 0;
  84.       rep(i, 0, n - 1) {
  85.         while (j1 < i && ab[j1].first < ab[i].first - k) {
  86.           c1.erase(ab[j1].second);
  87.           j1++;
  88.         }
  89.         while (j2 < i && ba[j2].first < ba[i].first - k) {
  90.           c2.erase(ba[j2].second);
  91.           j2++;
  92.         }
  93.         auto it = c1.lower_bound(ab[i].second);
  94.         it--;
  95.         l[ab[i].second] = max(l[ab[i].second], *it);
  96.         r[ba[i].second] = min(r[ba[i].second], *(c2.upper_bound(ba[i].second)));
  97.         c1.insert(ab[i].second);
  98.         c2.insert(ba[i].second);
  99.       }
  100.       j1 = n - 1; j2 = n - 1;
  101.       c1.clear(); c2.clear(); c1.insert(-1); c2.insert(n);
  102.       rev(i, n - 1, 0) {
  103.         while (j1 > i && ab[j1].first > ab[i].first + k) {
  104.           c1.erase(ab[j1].second);
  105.           j1--;
  106.         }
  107.         while (j2 > i && ba[j2].first > ba[i].first + k) {
  108.           c2.erase(ba[j2].second);
  109.           j2--;
  110.         }
  111.         auto it = c1.lower_bound(ab[i].second);
  112.         it--;
  113.         l[ab[i].second] = max(l[ab[i].second], *it);
  114.         r[ba[i].second] = min(r[ba[i].second], *(c2.upper_bound(ba[i].second)));
  115.         c1.insert(ab[i].second);
  116.         c2.insert(ba[i].second);
  117.       }
  118.       bool can = (!all_bad(0, n - 1));
  119.       if (can) hi = k;
  120.       else lo = k + 1;
  121.     }
  122.     return lo;
  123.   }
  124. };
  125.  
  126. // BEGIN CUT HERE
  127. #include <cstdio>
  128. #include <ctime>
  129. #include <iostream>
  130. #include <string>
  131. #include <vector>
  132. namespace moj_harness {
  133. 	using std::string;
  134. 	using std::vector;
  135. 	int run_test_case(int);
  136. 	void run_test(int casenum = -1, bool quiet = false) {
  137. 		if (casenum != -1) {
  138. 			if (run_test_case(casenum) == -1 && !quiet) {
  139. 				std::cerr << "Illegal input! Test case " << casenum << " does not exist." << std::endl;
  140. 			}
  141. 			return;
  142. 		}
  143.  
  144. 		int correct = 0, total = 0;
  145. 		for (int i=0;; ++i) {
  146. 			int x = run_test_case(i);
  147. 			if (x == -1) {
  148. 				if (i >= 100) break;
  149. 				continue;
  150. 			}
  151. 			correct += x;
  152. 			++total;
  153. 		}
  154.  
  155. 		if (total == 0) {
  156. 			std::cerr << "No test cases run." << std::endl;
  157. 		} else if (correct < total) {
  158. 			std::cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << std::endl;
  159. 		} else {
  160. 			std::cerr << "All " << total << " tests passed!" << std::endl;
  161. 		}
  162. 	}
  163.  
  164. 	int verify_case(int casenum, const int &expected, const int &received, std::clock_t elapsed) { 
  165. 		std::cerr << "Example " << casenum << "... "; 
  166.  
  167. 		string verdict;
  168. 		vector<string> info;
  169. 		char buf[100];
  170.  
  171. 		if (elapsed > CLOCKS_PER_SEC / 200) {
  172. 			std::sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
  173. 			info.push_back(buf);
  174. 		}
  175.  
  176. 		if (expected == received) {
  177. 			verdict = "PASSED";
  178. 		} else {
  179. 			verdict = "FAILED";
  180. 		}
  181.  
  182. 		std::cerr << verdict;
  183. 		if (!info.empty()) {
  184. 			std::cerr << " (";
  185. 			for (size_t i=0; i<info.size(); ++i) {
  186. 				if (i > 0) std::cerr << ", ";
  187. 				std::cerr << info[i];
  188. 			}
  189. 			std::cerr << ")";
  190. 		}
  191. 		std::cerr << std::endl;
  192.  
  193. 		if (verdict == "FAILED") {
  194. 			std::cerr << "    Expected: " << expected << std::endl; 
  195. 			std::cerr << "    Received: " << received << std::endl; 
  196. 		}
  197.  
  198. 		return verdict == "PASSED";
  199. 	}
  200.  
  201. 	int run_test_case(int casenum__) {
  202. 		switch (casenum__) {
  203. 		case 0: {
  204. 			int len                   = 6;
  205. 			int init[]                = {8,1,10,2,9,7};
  206. 			int a                     = 12;
  207. 			int b                     = 34;
  208. 			int c                     = 56;
  209. 			int d                     = 78;
  210. 			int m                     = 2;
  211. 			int expected__            = 1;
  212.  
  213. 			std::clock_t start__      = std::clock();
  214. 			int received__            = FindingFriends().shortestDistance(len, vector <int>(init, init + (sizeof init / sizeof init[0])), a, b, c, d, m);
  215. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  216. 		}
  217. 		case 1: {
  218. 			int len                   = 7;
  219. 			int init[]                = {1};
  220. 			int a                     = 1;
  221. 			int b                     = 0;
  222. 			int c                     = 0;
  223. 			int d                     = 12345678;
  224. 			int m                     = 5;
  225. 			int expected__            = 0;
  226.  
  227. 			std::clock_t start__      = std::clock();
  228. 			int received__            = FindingFriends().shortestDistance(len, vector <int>(init, init + (sizeof init / sizeof init[0])), a, b, c, d, m);
  229. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  230. 		}
  231. 		case 2: {
  232. 			int len                   = 12;
  233. 			int init[]                = {0};
  234. 			int a                     = 1;
  235. 			int b                     = 0;
  236. 			int c                     = 1;
  237. 			int d                     = 6;
  238. 			int m                     = 3;
  239. 			int expected__            = 0;
  240.  
  241. 			std::clock_t start__      = std::clock();
  242. 			int received__            = FindingFriends().shortestDistance(len, vector <int>(init, init + (sizeof init / sizeof init[0])), a, b, c, d, m);
  243. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  244. 		}
  245. 		case 3: {
  246. 			int len                   = 10;
  247. 			int init[]                = {3,4,5};
  248. 			int a                     = 23;
  249. 			int b                     = 34;
  250. 			int c                     = 35;
  251. 			int d                     = 46;
  252. 			int m                     = 4;
  253. 			int expected__            = 4;
  254.  
  255. 			std::clock_t start__      = std::clock();
  256. 			int received__            = FindingFriends().shortestDistance(len, vector <int>(init, init + (sizeof init / sizeof init[0])), a, b, c, d, m);
  257. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  258. 		}
  259. 		case 4: {
  260. 			int len                   = 2;
  261. 			int init[]                = {0,1000000000};
  262. 			int a                     = 0;
  263. 			int b                     = 0;
  264. 			int c                     = 0;
  265. 			int d                     = 1;
  266. 			int m                     = 2;
  267. 			int expected__            = 1000000000;
  268.  
  269. 			std::clock_t start__      = std::clock();
  270. 			int received__            = FindingFriends().shortestDistance(len, vector <int>(init, init + (sizeof init / sizeof init[0])), a, b, c, d, m);
  271. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  272. 		}
  273. 		case 5: {
  274. 			int len                   = 5;
  275. 			int init[]                = {1,2,1000,3,4};
  276. 			int a                     = 9;
  277. 			int b                     = 8;
  278. 			int c                     = 7;
  279. 			int d                     = 10;
  280. 			int m                     = 3;
  281. 			int expected__            = 996;
  282.  
  283. 			std::clock_t start__      = std::clock();
  284. 			int received__            = FindingFriends().shortestDistance(len, vector <int>(init, init + (sizeof init / sizeof init[0])), a, b, c, d, m);
  285. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  286. 		}
  287. 		case 6: {
  288. 			int len                   = 100000;
  289. 			int init[]                = {565990974};
  290. 			int a                     = 168649977;
  291. 			int b                     = 191924440;
  292. 			int c                     = 138092623;
  293. 			int d                     = 192724723;
  294. 			int m                     = 100000;
  295. 			int expected__            = 373269838;
  296.  
  297. 			std::clock_t start__      = std::clock();
  298. 			int received__            = FindingFriends().shortestDistance(len, vector <int>(init, init + (sizeof init / sizeof init[0])), a, b, c, d, m);
  299. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  300. 		}
  301.  
  302. 		// custom cases
  303.  
  304. /*      case 7: {
  305. 			int len                   = ;
  306. 			int init[]                = ;
  307. 			int a                     = ;
  308. 			int b                     = ;
  309. 			int c                     = ;
  310. 			int d                     = ;
  311. 			int m                     = ;
  312. 			int expected__            = ;
  313.  
  314. 			std::clock_t start__      = std::clock();
  315. 			int received__            = FindingFriends().shortestDistance(len, vector <int>(init, init + (sizeof init / sizeof init[0])), a, b, c, d, m);
  316. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  317. 		}*/
  318. /*      case 8: {
  319. 			int len                   = ;
  320. 			int init[]                = ;
  321. 			int a                     = ;
  322. 			int b                     = ;
  323. 			int c                     = ;
  324. 			int d                     = ;
  325. 			int m                     = ;
  326. 			int expected__            = ;
  327.  
  328. 			std::clock_t start__      = std::clock();
  329. 			int received__            = FindingFriends().shortestDistance(len, vector <int>(init, init + (sizeof init / sizeof init[0])), a, b, c, d, m);
  330. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  331. 		}*/
  332. /*      case 9: {
  333. 			int len                   = ;
  334. 			int init[]                = ;
  335. 			int a                     = ;
  336. 			int b                     = ;
  337. 			int c                     = ;
  338. 			int d                     = ;
  339. 			int m                     = ;
  340. 			int expected__            = ;
  341.  
  342. 			std::clock_t start__      = std::clock();
  343. 			int received__            = FindingFriends().shortestDistance(len, vector <int>(init, init + (sizeof init / sizeof init[0])), a, b, c, d, m);
  344. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  345. 		}*/
  346. /*      case 10: {
  347. 			int len                   = ;
  348. 			int init[]                = ;
  349. 			int a                     = ;
  350. 			int b                     = ;
  351. 			int c                     = ;
  352. 			int d                     = ;
  353. 			int m                     = ;
  354. 			int expected__            = ;
  355.  
  356. 			std::clock_t start__      = std::clock();
  357. 			int received__            = FindingFriends().shortestDistance(len, vector <int>(init, init + (sizeof init / sizeof init[0])), a, b, c, d, m);
  358. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  359. 		}*/
  360. /*      case 11: {
  361. 			int len                   = ;
  362. 			int init[]                = ;
  363. 			int a                     = ;
  364. 			int b                     = ;
  365. 			int c                     = ;
  366. 			int d                     = ;
  367. 			int m                     = ;
  368. 			int expected__            = ;
  369.  
  370. 			std::clock_t start__      = std::clock();
  371. 			int received__            = FindingFriends().shortestDistance(len, vector <int>(init, init + (sizeof init / sizeof init[0])), a, b, c, d, m);
  372. 			return verify_case(casenum__, expected__, received__, clock()-start__);
  373. 		}*/
  374. 		default:
  375. 			return -1;
  376. 		}
  377. 	}
  378. }
  379.  
  380.  
  381. int main() {
  382. #ifdef loc
  383.   if(!freopen((string(FOLDER) + "inp.txt").c_str(), "r", stdin)) {
  384.     assert(0);
  385.   }
  386.   freopen((string(FOLDER) + "out.txt").c_str(), "a", stdout);
  387.   freopen((string(FOLDER) + "out.txt").c_str(), "a", stderr);
  388. #endif
  389.   moj_harness::run_test();
  390. }
  391.  
  392. // END CUT HERE
  393.  
Time limit exceeded #stdin #stdout #stderr 5s 10840KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Example 0... PASSED
Example 1... PASSED
Example 2... PASSED
Example 3... PASSED
Example 4... PASSED
Example 5... PASSED
https://ideone.com/K9Jdoo
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!