fork download
copy 
  1. import java.util.Scanner;
  2. import java.util.StringTokenizer;
  3. import java.util.Vector;
  4. import java.util.*;
  5.  
  6. public class Main
  7. {
  8.  
  9. 	public interface SegmentedArray<Comparable>
  10. 	{
  11. 		int indexOf(Comparable value, int fromIndex);
  12.  
  13. 		void set(int fromIndex, int toIndex, Comparable value);
  14.  
  15. 		Comparable min(int fromIndex, int toIndex);
  16. 	}
  17.  
  18. 	public class SegmentedArrayImpl<Item extends Comparable<Item>> implements SegmentedArray<Item>
  19. 	{
  20. 		private int size;
  21. 		private int segmentSize;
  22. 		private Object[][] segments;
  23.  
  24. 		public SegmentedArrayImpl(int aSegmentSize, int aSegmentCount)
  25. 		{
  26. 			segmentSize = aSegmentSize;
  27. 			size = segmentSize * aSegmentCount;
  28.  
  29. 			segments = new Object[aSegmentCount][segmentSize];
  30. 		}
  31.  
  32. 		public int indexOf(Item value, int fromIndex)
  33. 		{
  34. 			if (fromIndex >= size)
  35. 			{
  36. 				return -1;
  37. 			}
  38.  
  39.  
  40. 			int segmentIndex = findSegmentIndex(fromIndex);
  41. 			int indexInSegment = fromIndex - segmentIndex * segmentSize;
  42.  
  43. 			while (segmentIndex < segments.length)
  44. 			{
  45. 			// @SuppressWarnings("unchecked")
  46. 			   if (((Item) (segments[segmentIndex][indexInSegment])).compareTo(value) == 0)
  47. 			   {
  48. 			   	return segmentIndex * indexInSegment;
  49. 			   }
  50.  
  51. 			   indexInSegment++;
  52.  
  53. 			   if (indexInSegment == segmentSize)
  54. 			   {
  55. 			   	indexInSegment = 0;
  56. 			   	segmentIndex++;
  57. 			   }
  58. 			}
  59.  
  60. 			return -1;
  61. 		}
  62.  
  63. 		public void set(int fromIndex, int toIndex, Item value)
  64. 		{
  65. 			if (fromIndex >= size || toIndex >= size || fromIndex > toIndex)
  66. 			{
  67. 				return;
  68. 			}	
  69.  
  70. 			int index = fromIndex;
  71. 			int segmentIndex = findSegmentIndex(fromIndex);
  72. 			int indexInSegment = fromIndex - segmentIndex * segmentSize;
  73.  
  74. 			while (segmentIndex < segments.length && index <= toIndex)
  75. 			{
  76. 			// @SuppressWarnings("unchecked")
  77. 			segments[segmentIndex][indexInSegment] = value;
  78. 			index++;
  79. 			indexInSegment++;
  80.  
  81. 			   if (indexInSegment == segmentSize)
  82. 			   {
  83. 			   	indexInSegment = 0;
  84. 			   	segmentIndex++;
  85. 			   }
  86. 			}
  87. 		}
  88.  
  89. 		public Item min(int fromIndex, int toIndex)
  90. 		{
  91. 			if (fromIndex >= size || toIndex >= size || fromIndex > toIndex)
  92. 			{
  93. 				return null;
  94. 			}
  95.  
  96. 			int index = fromIndex;
  97. 			int segmentIndex = findSegmentIndex(fromIndex);
  98. 			int indexInSegment = fromIndex - segmentIndex * segmentSize;
  99. 			Item minimum = null;
  100.  
  101. 			while (segmentIndex < segments.length && index < toIndex)
  102. 			{
  103. 			// @SuppressWarnings("unchecked")
  104. 			   Item val = (Item) segments[segmentIndex][indexInSegment];
  105. 			   if (minimum == null || val.compareTo(minimum) < 0)
  106. 			   {
  107. 			   	minimum = val;
  108. 			   }
  109.  
  110. 			   index++;
  111. 			   indexInSegment++;
  112.  
  113. 			   if (indexInSegment == segmentSize)
  114. 			   {
  115. 			   	indexInSegment = 0;
  116. 			   	segmentIndex++;
  117. 			   }
  118. 			}
  119.  
  120. 			return null;
  121. 		}
  122.  
  123. 		// check if the absolute index falls into given segment index
  124. 		private int compareIndexToSegment(int index, int segmentIndex)
  125. 		{
  126. 			int lowerIndex = segmentIndex * segmentSize;
  127. 			int higherIndex = (segmentIndex + 1) * segmentSize - 1;
  128.  
  129. 			if (index < lowerIndex) // index falls before segment
  130. 			{
  131. 			   return -1;
  132. 			} 
  133. 			else if (index > higherIndex) // index falls after segment
  134. 			{
  135. 			   return 1;
  136. 			}
  137.  
  138. 			return 0;
  139. 		}
  140.  
  141. 		// find segment that contains given absolute index using binary search
  142. 		  // in array
  143. 		private int findSegmentIndex(int index)
  144. 		{
  145. 			int lo = 0; // lower segment index
  146. 			int hi = segments.length - 1; // higher segment index
  147.  
  148. 			while (lo <= hi)
  149. 			{
  150. 			   int mid = lo + (hi - lo) / 2; // middle segment index
  151. 			   int cmp = compareIndexToSegment(index, mid);
  152.  
  153. 			   if (cmp < 0)
  154. 			   {
  155. 					hi = mid - 1;
  156. 			   }
  157.             else if (cmp > 0)
  158.             {
  159.             	lo = mid + 1;
  160.             }		
  161. 			   else if (cmp == 0)
  162. 			   {
  163. 			   	return mid;
  164. 			   }				
  165. 			}
  166.  
  167. 			return lo;
  168. 		}
  169.  
  170. 		public void show()
  171. 		{
  172. 			for (int i = 0; i < segments.length; i++)
  173. 			{
  174. 			   System.out.printf("segment#%d { ", i);
  175.  
  176. 			   for (int j = 0; j < segmentSize; j++)
  177. 			   {
  178. 				   System.out.print((Item) segments[i][j]);
  179. 				   System.out.print(" ");
  180. 			   }
  181.  
  182. 			   System.out.printf("}\n");
  183. 			}
  184. 		}
  185.  
  186. 	}
  187.  
  188. 	public static Vector<String> parseTextToTokens(String text)
  189. 	{
  190. 		Vector<String> tokens = new Vector<String>();
  191. 		StringTokenizer st = new StringTokenizer(text);
  192.  
  193. 		while (st.hasMoreTokens())
  194. 		{
  195. 			tokens.add(st.nextToken());
  196. 		}
  197.  
  198. 		return tokens;
  199. 	}
  200.  
  201. 	public static Integer strToInt(String s)
  202. 	{
  203. 		Integer x = null;
  204. 		try
  205. 		{
  206. 			x = Integer.parseUnsignedInt(s);
  207. 		}
  208. 		catch (NumberFormatException e)
  209. 		{
  210. 		}
  211.  
  212. 		return x;
  213. 	}
  214.  
  215. 	public static void main(String[] args)
  216. 	{
  217. 		Main obj = new Main();
  218. 		SegmentedArrayImpl<String> storage = obj.new SegmentedArrayImpl<String>(4, 4);
  219.  
  220. 		Scanner in = new Scanner(System.in);
  221.  
  222. 		for (;;)
  223. 		{
  224. 			String inputLine = in.nextLine();
  225.  
  226. 			if (inputLine.isEmpty())
  227. 			{
  228. 			   continue;
  229. 			}
  230.  
  231. 			String cmd = null;
  232. 			String arg1 = null;
  233. 			String arg2 = null;
  234. 			String arg3 = null;
  235.  
  236. 			Vector<String> inputTokens = parseTextToTokens(inputLine);
  237.  
  238. 			if (inputTokens.size() > 0)
  239. 			{
  240. 				cmd = inputTokens.get(0);
  241. 			}
  242. 			if (inputTokens.size() > 1)
  243. 			{
  244. 				arg1 = inputTokens.get(1);
  245. 			}
  246. 			if (inputTokens.size() > 2)
  247. 			{
  248. 				arg2 = inputTokens.get(2);
  249. 			}
  250. 			if (inputTokens.size() > 3)
  251. 			{
  252. 				arg3 = inputTokens.get(3);
  253. 			}
  254.  
  255. 			if (cmd.equals("exit"))
  256. 			{
  257. 			   break;
  258. 			}
  259. 			else if (cmd.equals("show"))
  260. 			{
  261. 			   storage.show();
  262. 			}
  263. 			else if (cmd.equals("index"))
  264. 			{
  265. 			   String value = (arg1 != null && !arg1.isEmpty()) ? arg1 : null;
  266. 			   Integer fromIndex = (arg2 != null) ? strToInt(arg2) : null;
  267.  
  268. 			   if (value == null || fromIndex == null)
  269. 			   {
  270. 			   	System.out.printf("*** ERROR: wrong arguments: <%s> <%s> <%d>\n", cmd, arg1, arg2);
  271. 				   continue;
  272. 			   }
  273.  
  274. 			   System.out.println(storage.indexOf(value, fromIndex));
  275. 			}
  276. 			else if (cmd.equals("set"))
  277. 			{
  278. 			   Integer fromIndex = (arg1 != null) ? strToInt(arg1) : null;
  279. 			   Integer toIndex = (arg2 != null) ? strToInt(arg2) : null;
  280. 			   String value = (arg3 != null && !arg3.isEmpty()) ? arg3 : null;
  281.  
  282. 			   if (fromIndex == null || toIndex == null || value == null)
  283. 			   {
  284. 				   System.out.printf("*** ERROR: wrong arguments: <%s> <%d> <%d> <%s>\n", cmd, arg1, arg2, arg3);
  285. 				   continue;
  286. 			   }
  287.  
  288. 			   storage.set(fromIndex, toIndex, value);
  289. 			   System.out.println("Ok");
  290. 			}
  291. 			else if (cmd.equals("min"))
  292. 			{
  293. 			   Integer fromIndex = (arg1 != null) ? strToInt(arg1) : null;
  294. 			   Integer toIndex = (arg2 != null) ? strToInt(arg2) : null;
  295.  
  296. 			   if (fromIndex == null || toIndex == null)
  297. 			   {
  298. 			   	System.out.printf("*** ERROR: wrong arguments: <%s> <%d> <%d>\n", cmd, arg1, arg2);
  299. 			   	continue;
  300. 			   }
  301.  
  302. 			   System.out.println(storage.min(fromIndex, toIndex));
  303. 			}
  304. 		}
  305.  
  306. 		in.close();
  307. 	}
  308. }
  309.  
Success #stdin #stdout 0.14s 321280KB
comments (?)
stdin
copy 
set 2 2 H
set 3 3 E
set 4 5 L
set 6 6 O
set 8 8 W
set 9 9 O
set 10 10 R
set 11 11 L
set 12 12 D
set 13 13 !
set 14 14 !
set 15 15 !
show
exit
stdout
copy 
Ok
Ok
Ok
Ok
Ok
Ok
Ok
Ok
Ok
Ok
Ok
Ok
segment#0 { null null H E }
segment#1 { L L O null }
segment#2 { W O R L }
segment#3 { D ! ! ! }
https://ideone.com/BknxiN
language:
Java (12.0.1)
created:
8 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!