|
|
At first I converted all the things to indices. for example if n = 5 2 4 5 2 4 and m = 1 4 2 2 -> 1 - 2, and 4 - 5 <= these are all index. Then I got only some pair of index. From these I calculate the 11011. THere may be index intersections. That is my code. I think its time and algo is ok. But I got wa3 import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.Scanner; public class Timus1827 { public static void main(String [] args){ Scanner input = new Scanner(System.in); int n = input.nextInt(); int [] a = new int[n]; HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>(); for(int i = 0; i < n; i++){ a[n - i - 1] = input.nextInt(); if(map.get(a[n - i - 1]) == null){ map.put(a[n - i - 1], new ArrayList<Integer>()); } map.get(a[n - i - 1]).add(n - i - 1); } int m = input.nextInt(); int[] h = new int[n]; boolean[] dontuse = new boolean[n]; Arrays.fill(dontuse, false); Arrays.fill(h, -1); for(int i = 0; i < m; i++){ int x = input.nextInt(); int y = input.nextInt(); int d = input.nextInt() - 1; if(map.containsKey(x)) for(int j : map.get(x)){ if(j + d < n && a[j + d] == y){ h[j] = Math.max(h[j], j + d); dontuse[j] = true; } } } int k = -1; for(int i = 0; i < n; i++){ if(dontuse[i]) { k = i; break; } } int j = k; for(int i = k + 1; i < n; i++){ if(dontuse[i]){ if(h[j] + 1 >= i){ h[j] = h[i]; dontuse[i] = false; } else{ j = i; } } } int[] ans = new int[n]; Arrays.fill(ans, 0); for(int i = 0; i <n; i++){ if(dontuse[i]){ for(j = i; j <= h[i]; j++){ ans[j] = 1; } } } for (int i = 0; i < n; i++) System.out.print(ans[i]); } } Please somebody help me to solve this problem. Show me my mistake in algo or tell me the hint to solve it reverse(ans.begin(), ans.end()); my algo should be n*50*order of hash probably large input is causing problem i can use fread and fwrite but don't know how to do it in online judge submission. please provide me with some code segment that utilize fread and fwrite. better be some eg problem as 1000. a+b problem thanks in advance. So did i. did you find some methods to solve it? please help me.thx a lot. yes. my hash was correct. but i used long long for calculation. i replaced with int except for one case and got ac. anyway my mod value for double hash was 499979. hash using just those 3 integers in 2e8 radix system and avoid long long as much as possible. good luck. anyway i still want to know the fread, fwrite magic. as so many problems i got ac in 0.015 sec but best timing was 0.001 sec. if u know, please help. Edited by author 29.03.2011 22:28 tle at test 22... Just some big test, probably without any 1's in the answer. To speed up your code, don't use stl structures - write your own hash. i have written my own hash to store m internal conflict and then check all n days.but also got tle. It is driving me mad! Do you have some better solutions? thx for help me. Edited by author 24.03.2011 16:11 Edited by author 24.03.2011 16:15 No, my solution is pretty straightforward - take every day and for all i from 1 to 50 check whether triple (a[n], a[i+n], i) occurs in the sequence that was read from the input. Overall complexity is O(50*n) assuming complexity of your hash is O(1) Edited by author 24.03.2011 16:22 I want know how to hash triple(ai,bi,di)..i use a list hash[len][ai] and scan it.I think it is the reason i got tle... still tle or wa... AC with STL Hashing is somthing terrible. 1)form all possible segments ;2) sort it 3) find all belongings for each given conflict; 3) apply segment union - O(n) algo(very important! classical!) Sent on timus_support a couple of good tests, which my program that works 0.25 sec on timus, passes in about 1 minute on my PC Your tests were added. Thank you. What's the answer for these tests? #1 8 4 3 2 1 4 3 2 1 2 1 2 2 3 4 2 #2 8 4 3 2 1 4 3 2 1 2 3 4 2 1 2 2 thanks. Any admin is here? And you'd think that the admin is sitting all the time on the site and solving to test these examples? :) Powers of all the numbers in statement was disappeared. Restore them, please. My browser is Opera 11.01. Yes, this is a known bug and it appears in some other problems with sub/superscripts. Everything is ok in english statements btw. what answer for 3 6 5 4 1 1 5 5 I think, it is 011 it's right? edited: no, answer is 000 Edited by author 20.03.2011 09:53 TL with scanf / putchar AC with fread / fwrite (0.281 s) Don't like problems with such hacks :\ Sorry, my bad. Anyway, can natives be at war more than n days ago? For example, what's the answer for this test: 1 1 1 2 1 2 ? Edited by author 19.03.2011 16:41 Can various fightings begin in one day? |
|
|