Show all threads Hide all threads Show all messages Hide all messages |
How fast can you solve it for the case d <= n? | ARK (***AESC_USU***) | 1827. Indigenous Wars | 16 Jan 2018 07:51 | 1 |
|
Please can you help me why my prog gives wa3 | Ibragim Atadjanov (Tashkent U of IT) | 1827. Indigenous Wars | 16 Mar 2013 16:41 | 3 |
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()); |
I use double hash but still tle. and i do not know how to use fread, fwrite in online judge,please help | muhammad | 1827. Indigenous Wars | 29 Mar 2011 22:26 | 3 |
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 |
what is test 22? | tracyzhu | 1827. Indigenous Wars | 26 Mar 2011 13:06 | 7 |
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... 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!) |
2 ADMINS: Weak tests | Vedernikoff 'Goryinyich' Sergey (HSE: АОП) | 1827. Indigenous Wars | 25 Mar 2011 18:52 | 2 |
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? | enoyps | 1827. Indigenous Wars | 25 Mar 2011 14:52 | 3 |
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. And you'd think that the admin is sitting all the time on the site and solving to test these examples? :) |
Fix the statement's text, please. | olpetOdessaONU [1 2/3] | 1827. Indigenous Wars | 20 Mar 2011 18:23 | 2 |
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? | Vit Demidenko | 1827. Indigenous Wars | 19 Mar 2011 22:59 | 1 |
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 |
Fast IO helped me. | Vasya.V | 1827. Indigenous Wars | 19 Mar 2011 21:06 | 1 |
TL with scanf / putchar AC with fread / fwrite (0.281 s) Don't like problems with such hacks :\ |
Explain sample please | 2rf | 1827. Indigenous Wars | 19 Mar 2011 16:28 | 1 |
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 |
question.. | MOPDOBOPOT (USU) | 1827. Indigenous Wars | 19 Mar 2011 16:23 | 1 |
Can various fightings begin in one day? |