TLE#6 C# Posted by Sadeko 29 Mar 2019 19:37 I wrote 2 different codes and both failed the sixth Test. Please, help me! --------------------------------------------------------------------------------------- Code #1 (BinaryTree): using System; using System.Collections.Generic; namespace ConsoleApp35 { class Program { class TreeNode { public TreeNode left { get; set; } public TreeNode right { get; set; } public uint data1; public int data2; } class BinaryTree { public TreeNode root = null; public void AddRoot(uint data1, int data2) { TreeNode n = new TreeNode(); n.data1 = data1; n.data2 = data2; root = n; return; } public void Add(uint data1, int data2) { TreeNode n = new TreeNode(); n.data1 = data1; n.data2 = data2; TreeNode current = root; while (true) { if (n.data1 < current.data1) { if (current.left == null) { current.left = n; return; } else current = current.left; } else { if (current.right == null) { current.right = n; return; } else current = current.right; } } } public TreeNode Search(uint data1, TreeNode node) { if (node == null) return null; else if (node.data1 == data1) return node; else if (data1 < node.data1) return Search(data1, node.left); else return Search(data1, node.right); } public TreeNode ModifySearch(uint data1, TreeNode node, uint l, uint r) { if (node == null) return null; else if (node.data1 == data1 && node.data2 >= l && node.data2 <= r) return node; else if (data1 < node.data1) return ModifySearch(data1, node.left, l, r); else return ModifySearch(data1, node.right, l, r); } } static void Main(string[] args) { BinaryTree BT = new BinaryTree();
int n = int.Parse(Console.ReadLine()); var s = Console.ReadLine().Split(); BT.AddRoot(uint.Parse(s[0]), 1); for (int i = 1; i < n; i++) BT.Add(uint.Parse(s[i]), i+1); int q = int.Parse(Console.ReadLine()); uint[,] lrx = new uint[q, 3]; string res = ""; for (int i = 0; i < q; i++) { s = Console.ReadLine().Split(); lrx[i, 0] = uint.Parse(s[0]); lrx[i, 1] = uint.Parse(s[1]); lrx[i, 2] = uint.Parse(s[2]);
TreeNode a = BT.ModifySearch(lrx[i, 2], BT.root, lrx[i, 0], lrx[i, 1]); if (a == null) res += '0'; else res += '1'; } Console.WriteLine(res); } } } --------------------------------------------------------------------------------------- Code #2 (QuickSort + BinarySearch): using System; namespace ConsoleApp34 { class Program { public static int Partition(ref int[] a, int down, int up) { int pivot = a[down]; int index = down; int i = down + 1, j = up; while (true) { while (a[i] <= pivot && i <= up - 1) i++; while (a[j] >= pivot && j >= down + 1) j--; if (i >= j) { int tmp = a[index]; a[index] = a[j]; a[j] = tmp; return j; } int temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j--; } }
public static void QuickSort(ref int[] a, int down, int up) { if (down < up) { int p = Partition(ref a, down, up); QuickSort(ref a, down, p - 1); QuickSort(ref a, p + 1, up); } } public static int BS(int[] a, int key) { int l = 0; int r = a.Length - 1; while (l < r - 1) { int m = l + (r - l) / 2; if (a[m] < key) l = m; else r = m; } if (a[l].CompareTo(key) == 0) return l; if (a[r].CompareTo(key) == 0) return r; return -1; } static void Main(string[] args) { int n = int.Parse(Console.ReadLine()); int[] a = new int[n]; int[] a_copy = new int[n]; int[] keys = new int[n]; var s = Console.ReadLine().Split(); for (int i = 0; i < n; i++) { a[i] = int.Parse(s[i]); a_copy[i] = int.Parse(s[i]); } QuickSort(ref a,0,a.Length-1); for (int i = 0; i < a.Length; i++) for (int j = 0; j < a.Length; j++) { if (a[i] == a_copy[j]) { keys[i] = j + 1; a_copy[j] = -1; break; } } int q = int.Parse(Console.ReadLine()); int[] l = new int[q]; int[] r = new int[q]; int[] x = new int[q]; string res = ""; for (int i = 0; i < q; i++) { s = Console.ReadLine().Split(); l[i] = int.Parse(s[0]); r[i] = int.Parse(s[1]); x[i] = int.Parse(s[2]);
int index = BS(a, x[i]); int j = index; bool b = false; while (j >= 0 && j < a.Length && a[j] == a[index]) { int realPlace = keys[j++]; if (realPlace <= r[i] && realPlace >= l[i]) { res += '1'; b = true; break; } } if (!b) res += '0'; } Console.WriteLine(res); } } } Edited by author 29.03.2019 19:45 Re: TLE#6 C# Posted by Sadeko 31 Mar 2019 00:03 The improved second code also fails the sixth test (TLE). using System; using System.Collections.Generic; namespace ConsoleApp34 { class Node { public int data1; public int data2; } class Program { public static int modifyPartition(ref Node[] a, int down, int up) { int pivot = a[down].data1; int index = down; int i = down + 1, j = up; while (true) { while (a[i].data1 <= pivot && i <= up - 1) i++; while (a[j].data1 >= pivot && j >= down + 1) j--; if (i >= j) { int tmp1 = a[index].data1; int tmp2 = a[index].data2; a[index].data1 = a[j].data1; a[index].data2 = a[j].data2; a[j].data1 = tmp1; a[j].data2 = tmp2; return j; } int temp1 = a[i].data1; int temp2 = a[i].data2; a[i].data1 = a[j].data1; a[i].data2 = a[j].data2; a[j].data1 = temp1; a[j].data2 = temp2; i++; j--; } } public static void modifyQS(ref Node[] a, int down, int up) { if (down < up) { int p = modifyPartition(ref a, down, up); modifyQS(ref a, down, p - 1); modifyQS(ref a, p + 1, up); } } public static int modifyBS(Node[] a, int key) { int l = 0; int r = a.Length - 1; while (l < r - 1) { int m = l + (r - l) / 2; if (a[m].data1 < key) l = m; else r = m; } if (a[l].data1.CompareTo(key) == 0) return l; if (a[r].data1.CompareTo(key) == 0) return r; return -1; } static void Main(string[] args) { int n = int.Parse(Console.ReadLine()); Node[] info = new Node[n]; var s = Console.ReadLine().Split(); for (int i = 0; i < n; i++) { info[i] = new Node(); info[i].data1 = int.Parse(s[i]); info[i].data2 = i+1; }
modifyQS(ref info, 0, info.Length - 1); int q = int.Parse(Console.ReadLine()); int[] l = new int[q]; int[] r = new int[q]; int[] x = new int[q]; string res = "";
for (int i = 0; i < q; i++) { s = Console.ReadLine().Split(); l[i] = int.Parse(s[0]); r[i] = int.Parse(s[1]); x[i] = int.Parse(s[2]);
int index = modifyBS(info, x[i]); int j = index; bool b = false; while (j >= 0 && j < info.Length && info[j].data1 == info[index].data1) { if (info[j].data2 <= r[i] && info[j].data2 >= l[i]) { res += '1'; b = true; break; } j++; } if (!b) res += '0'; } Console.WriteLine(res); } } } |