0
Your rating: None

CodeChef submission 62926 (C++ 4.0.0-8)

CodeChef submission 62926 (C++ 4.0.0-8) plaintext list. Status: TLE, problem F1, contest AUG09. By gmark (Mark Greve), 2009-08-02 20:38:12.
  1. // Golf Course
  2. // Source: CodeChef August 2009 Algorithm Challenge
  3. // CodeChef ID: F1
  4. // Date: 02-08-2009
  5. // Author: Mark Greve
  6.  
  7. #include <algorithm>
  8. #include <bitset>
  9. #include <cassert>
  10. #include <cctype>
  11. #include <cmath>
  12. #include <cstdio>
  13. #include <cstdlib>
  14. #include <cstring>
  15. #include <ctime>
  16. #include <deque>
  17. #include <functional>
  18. #include <iomanip>
  19. #include <iostream>
  20. #include <list>
  21. #include <map>
  22. #include <numeric>
  23. #include <queue>
  24. #include <set>
  25. #include <sstream>
  26. #include <stack>
  27. #include <string>
  28. #include <utility>
  29. #include <vector>
  30. using namespace std;
  31.  
  32. // FAST IO
  33. char *start;
  34. const int MAXBUF=10000000;
  35. char buf[MAXBUF];
  36. char outbuf[MAXBUF];
  37. int outat;
  38. void skip() {
  39. 	while (*start != 0  && !('0' <= *start && *start <= '9')) start++;
  40. }
  41. void GETNUM(int& n){
  42. 	skip();
  43. 	n=0;
  44. 	while ('0' <= *start && *start <= '9') {
  45. 		n = n*10 + *start-'0', ++start;
  46. 	}
  47. }
  48. void take_input() { // Take input using fast I/O
  49. 	int sz=fread(buf, sizeof(char), MAXBUF, stdin);
  50. 	buf[sz]=0;
  51. 	start=buf;
  52. 	outat=0;
  53. }
  54.  
  55. void outc(char c) { outbuf[outat++] = c; }
  56. void out(int x) {
  57. 	char s[100]; int at = 0;
  58. 	do { s[at++] = x%10, x/=10; } while(x>0);
  59. 	for (int i=at-1;i>=0;--i) outbuf[outat++] = s[i]+'0';
  60. }
  61. void flushoutbuf() {
  62. 	//fwrite(outbuf, sizeof(char),outat,stdout);
  63. 	outbuf[outat++]='\0';
  64. 	printf("%s", outbuf);
  65. }
  66. // END FAST IO
  67.  
  68. typedef long long LL;
  69. const int BITS=14;
  70. const int MAX=1<<BITS;
  71.  
  72. int val(LL x) { return x&((1<<(BITS))-1); }
  73. int num(LL x) { return x>>BITS; }
  74.  
  75.  
  76. /*
  77. // A simple bit trie to speed up the computation
  78. LL gcnt[2*MAX];
  79. int val(LL x) { return x&((1<<(BITS))-1); }
  80. int num(LL x) { return x>>BITS; }
  81. vector<pair<int,int> > ops;
  82. void insert(int f, int am) { 
  83. 	//printf("INSERT %d AM: %d\n", f,am);
  84. 	ops.push_back(make_pair(f,am));
  85. 	f += MAX-1;
  86. 	gcnt[f] += am;
  87. 	while (f>0) f = (f-1)/2, gcnt[f] += am;
  88. }
  89. LL getmax() {
  90. 	int cur = 0, rc;
  91. 	for (int i=0;i<BITS;++i) {
  92. 		if (gcnt[rc=(2*cur+2)]>0) cur = rc;
  93. 		else cur = 2*cur + 1;
  94. 	}
  95. 	//printf("MINV: %d (%d)\n", cur-(MAX-1), gcnt[cur]);
  96. 	LL ret = (gcnt[cur]<<BITS) + cur-(MAX-1);
  97. 	//assert(val(ret)==cur-(MAX-1));
  98. 	//assert(num(ret)==gcnt[cur]);
  99. 	return ret;
  100. }
  101. void reset() {
  102. 	//printf("RESET........\n");
  103. 	if (1 || ops.size()<=100) {
  104. 		int sz = ops.size();
  105. 		for (int i=0;i<sz;++i) {
  106. 			insert(ops[i].first,-ops[i].second);
  107. 		}
  108. 	}
  109. 	else memset(gcnt,0,sizeof gcnt);
  110. 	ops.clear();
  111. }
  112. */
  113.  
  114. /*
  115. template <class T> struct stree {
  116. 	struct node {
  117. 		node *p, *l, *r;
  118. 		T key;
  119. 		int ss; // augmented data, subtree size
  120. 		int cnt; // count of the number of nodes with this key
  121. 		node(node* p=0, node* l=0, node* r=0) : p(p), l(l), r(r), cnt(1), ss(1) {}
  122. 		~node() { delete l, delete r; }
  123. 	};
  124. 	node* root;
  126. 	// Construct an empty splay tree
  127. 	stree() : root(0) {}
  128.  
  129. 	// Disassemble the tree
  130. 	~stree() { delete root; }
  131.  
  132. 	// Recompute information in a node (if needed)
  133. 	void update(node* x) {
  134. 		if (0==x) return;
  135. 		x->ss = x->cnt;
  136. 		if (0 != x->l) x->ss += x->l->ss;
  137. 		if (0 != x->r) x->ss += x->r->ss;
  138. 	}
  139.  
  140. 	// Rotate x one level up
  141. 	void rotate(node* x) {
  142. 		node* y = x->p; if (0==y) return;
  143. 		x->p = y->p;
  144. 		if (0 != y->p) (y->p->l == y) ? (y->p->l = x) : (y->p->r = x);
  145. 		y->p = x;
  146. 		if (y->l == x) {
  147. 			if (0 != x->r) x->r->p = y;
  148. 			y->l = x->r, x->r = y;
  149. 		}
  150. 		else {
  151. 			if (0 != x->l) x->l->p = y;
  152. 			y->r = x->l, x->l = y;
  153. 		}
  154. 		update(y), update(x), update(x->p);
  155. 	}
  156.  
  157. 	// Splay a node to the root
  158. 	void splay(node* x) {
  159. 		if (0==x) return;
  160. 		while (x->p != 0) {
  161. 			node* y = x->p;
  162. 			if (0 == y->p)
  163. 				rotate(x);
  164. 			else if ( (y->p->l == y && x == y->l) || (y->p->r == y && x == y->r) )
  165. 				rotate(y), rotate(x);
  166. 			else
  167. 				rotate(x), rotate(x);
  168. 		}
  169. 		root = x;
  170. 	}
  171.  
  172. 	node* search(const T& x) {
  173. 		for (node* cur = root; 0 != cur;) {
  174. 			if      (x < cur->key) { if (0!=cur->l) cur = cur->l; else return cur; }
  175. 			else if (x > cur->key) { if (0!=cur->r) cur = cur->r; else return cur; }
  176. 			else return cur;
  177. 		}
  178. 	}
  179.  
  180. 	// Returns the number of occurrences of x in the tree
  181. 	int count(const T& x) { return splay(search(x)), ((0!=root && x == root->key) ? root->cnt : 0); }
  182.  
  183. 	// Insert num copies of key x in the tree
  184. 	void insert(const T& x, int num=1) {
  185. 		if (0==root){root=new node;root->cnt=num;root->key=x;splay(root);return;}
  186. 		node* cur = search(x);
  187. 		if      (x < cur->key) cur->l = new node(cur), cur->l->cnt = num, cur->l->key = x, splay(cur->l);
  188. 		else if (x > cur->key) cur->r = new node(cur), cur->r->cnt = num, cur->r->key = x, splay(cur->r);
  189. 		else cur->cnt += num, splay(cur);
  190. 	}
  191.  
  192. 	// Erase num elements with key x (if there are less than num all are erased)
  193. 	void erase(const T& x, int num=1) {
  194. 		if (0==root) return;
  195. 		splay(search(x));	if (x != root->key) return;
  196. 		root->cnt -= num; if (root->cnt > 0) return;
  197. 		while (root->l != 0 && root->l->r != 0) rotate(root->l->r);
  198. 		node* tmp = root;
  199. 		if (0 == root->l && 0==root->r) root = 0;
  200. 		else if (0 == root->l) root = root->r, root->p = 0;
  201. 		else if (0 == root->r) root = root->l, root->p = 0;
  202. 		else root->l->r = root->r, root->l->r->p = root->l, root = root->l, root->p = 0;
  203. 		if (0!=root) update(root->l), update(root->r);
  204. 		update(root);
  205. 		tmp->l = tmp->r = 0;
  206. 		delete tmp;
  207. 	}
  208. };
  209.  
  211. stree<int> *st;
  212. void insert(int f, int am) { 
  213. 	//printf("INSERT %d %d\n", f,am);
  214. 	if (am<0) st->erase(f,-am);
  215. 	else st->insert(f,am);
  216. }
  217. LL getmax() { 
  218. 	stree<int>::node* x = st->search(1<<25);
  219. 	//printf("MAX: %d %d\n", x->key, x->cnt);
  220. 	LL ret =  ((LL(x->cnt))<<BITS) + LL(x->key);
  221. 	return ret;
  222. }
  223. void reset() {
  224. 	//printf("RESET\n");
  225. 	delete st;
  226. 	st = new stree<int>();
  227. }
  228. */
  229.  
  230. map<int,int> st;
  231. void insert(int f, int am) { 
  232. 	//printf("INSERT %d %d\n", f,am);
  233. 	if (am<0) st[f] -= am;
  234. 	else st[f] += am;
  235. }
  236. LL getmax() { 
  237. 	int key = (--st.end())->first;
  238. 	int cnt = (--st.end())->second;
  239. 	LL ret =  ((LL(cnt))<<BITS) + LL(key);
  240. 	return ret;
  241. }
  242. void reset() {
  243. 	//printf("RESET\n");
  244. 	st.clear();
  245. }
  246.  
  247. LL row[501][501];
  248. LL col[501][501];
  249. int A[501][501];
  250.  
  251. int main() {
  252. 	take_input();
  253.  
  254. 	int NCASES;
  255. 	GETNUM(NCASES);
  256. 	for (int z=1;z<=NCASES;++z) {
  257. 		int M,N,K;
  258. 		GETNUM(M);
  259. 		GETNUM(N);
  260. 		GETNUM(K);
  261.  
  262. 		for (int i=0;i<M;++i)
  263. 			for (int j=0;j<N;++j)
  264. 				GETNUM(A[i][j]);
  265.  
  266. 		// Precompute row values.
  267. 		for (int i=0;i<M;++i) {
  268. 			reset();
  269. 			for (int j=0;j<K;++j) insert(A[i][j],1);
  270.  
  271. 			for (int j=0;j<N-K+1;++j) {
  272. 				row[i][j] = getmax();
  273. 				if (j+1!=N-K+1) insert(A[i][j],-1), insert(A[i][j+K],1);
  274. 			}
  275. 		}
  276. 			
  277. 		// Precompute column values
  278. 		for (int j=0;j<N;++j) {
  279. 			reset();
  280. 			for (int i=0;i<K;++i) insert(A[i][j],1);
  281.  
  282. 			for (int i=0;i<M-K+1;++i) {
  283. 				col[i][j] = getmax();
  284. 				if (i+1!=M-K+1) insert(A[i][j],-1), insert(A[i+K][j],1);
  285. 			}
  286. 		}
  287. 		
  288. 		outc('C');
  289. 		outc('a');
  290. 		outc('s');
  291. 		outc('e');
  292. 		outc(' ');
  293. 		out(z);
  294. 		outc(':');
  295. 		outc('\n');
  296.  
  297. 		for (int i=0;i<M-K+1;++i) {
  298. 			reset();
  299. 			for (int k=0;k<K;++k) insert(val(col[i][k]), num(col[i][k]));
  300.  
  301. 			for (int j=0;j<N-K+1;++j) {
  302. 				if (j!=0) outc(' ');
  303. 				LL maxv = getmax();
  304. 				int v = val(maxv), cnt = num(maxv);
  305. 				out(v);
  306. 				if (cnt!=1) outc('('), out(cnt), outc(')');
  307.  
  308. 				if (j+1!=N-K+1) {
  309. 					insert(val(col[i][j+K]), num(col[i][j+K]));
  310. 					insert(val(col[i][j]), -num(col[i][j]));
  311. 				}
  312. 			}
  313. 			outc('\n');
  314. 		}
  315. 		outc('\n');
  316. 	}
  317. 	flushoutbuf();
  318. }
  319.

Comments