Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | Страница 4 | runtime error #1 | inkosta | 1003. Чётность | 1 фев 2022 21:52 | 1 | Is there any way I can see the output of my program? The message "Runtime error" is very uninformative, besides, on my computer, my program performs a variety of tests without any errors. | Solution | Alikhan Zimanov | 1003. Чётность | 16 авг 2022 01:26 | 4 | Solution Alikhan Zimanov 12 июл 2020 13:56 Let a[1], ... , a[n] be the sequence written by the friend and pref[i] be the xor of the prefix a[1...i]. Then a question (l, r, t) (which means the parity of the number of ones on the segment from l to r is t) can be represented as (pref[r] xor pref[l - 1] = t). Let's build a graph with two vertices for each prefix (thus, there will be 2 * (n + 1) vertices). Using compression, we actually need only at most 2 * m vertices (where m is the number of questions). Let the vertices corresponding to the prefix i be f0(i) and f1(i). Now, let's add all edges f0(i) ~ f1(i). For a question (pref[r] xor pref[l - 1] = t) if t = 1, we add two edges f0(l - 1) ~ f0(r) and f1(l - 1) ~ f1(r), else if t = 0, we add edges f0(l - 1) ~ f1(r) and f1(l - 1) ~ f0(r). To check whether a sequence of questions from 1 to x is achievable we just need to check whether our current graph is bipartite. This can be done by simply doing dfs after each question. Can you please elaborate in a few words? I actually didn't get the significance of having two vertices for each prefix and how it's solving the problem. | To Admins. Some test | Kirom `Ekexity [SESC17]💻 | 1003. Чётность | 17 май 2018 04:26 | 1 | Please Add it in tests! 20 10 1 1 even 4 4 even 2 2 odd 5 5 odd 1 3 even 3 5 odd 8 8 even 9 9 even 10 10 even 8 10 even -1 Correct answer is: 5 My AC prog give 10, but correct answer is 5 | Some hints | monsky | 1003. Чётность | 4 янв 2019 16:14 | 3 | Online tests surely contain several tests in one file, so: 1. Be sure clean your dictionaries before every test. 2. Be sure read ALL lines of current test, even you got correct answer before all input was used. This two issues were the reason of my WA1. After fixing them I got "Accepted". Use the following test to validate mentioned above points: 100 5 5 6 odd 7 8 odd 1 6 even 1 4 odd 7 8 even 3 3 1 1 odd 3 3 odd 1 3 odd 5 4 1 2 even 4 5 even 1 5 odd 3 3 even 10 5 1 2 even 3 4 odd 5 6 even 1 6 even 7 10 odd 20 8 1 9 odd 10 17 odd 18 26 odd 4 5 odd 27 40 even 21 40 odd 1 20 odd 10 20 odd 200 8 1 9 odd 10 17 odd 18 26 odd 4 5 odd 27 40 even 21 40 odd 1 20 odd 10 20 odd -1 Answer: 4 3 3 3 2 6 Why 6th answer is 2 rather than 6? | First number? | monsky | 1003. Чётность | 29 окт 2016 23:46 | 1 | It looks as first input number (sequence length) isn't needed for solution. | В условии неверно описан формат тестов | yz | 1003. Чётность | 10 апр 2020 14:24 | 2 | Извините, что по-русски, надеюсь, администраторы знают этот язык. В условии сказано, что длина последовательности задается в первой строке каждого теста. В примерах на форуме длина общая для всех, в каждом тесте задается только количество вопросов. Моя AC-программа действует по форуму: читает длину один раз, а потом только количество вопросов для каждого теста. Хорошо бы привести текст задачи в соответствие с реальностью. Совсем хорошо было бы дать в примере два теста, чтобы сделать структуру входных данных действительно ясной. | One test to rule them all | Afigan | 1003. Чётность | 13 май 2019 13:56 | 2 | 100000000 10 1 5 even 6 10 even 11 18 even 19 25 even 1 8 even 16 25 even 16 40 even 9 40 odd 1000 5000 odd 1000 6000 odd -1 answer: 7 why is it 7? could you explain? | Why always Memory limit exceeded??? | David Yin | 1003. Чётность | 12 июн 2016 17:35 | 2 | Why always Memory limit exceeded??? It is so wired. package com.island.timus.ahundrend; import java.util.Scanner; public class T1003_Parity { public static void main(String[] args) { Scanner in = new Scanner(System.in); int length = in.nextInt(); while (length != -1) { int[][] friendsAndEnemies = new int[2][length + 1]; for (int j = 0; j < length + 1; j++) { friendsAndEnemies[0][j] = j; friendsAndEnemies[1][j] = -1; } int conditions = in.nextInt(); int counter = 1; for (int i = counter; i <= conditions; i++, counter++) { Term.start = in.nextInt(); Term.end = in.nextInt(); Term.parity = in.nextLine(); if (Term.start > length || Term.end > length) { break; } if (Term.parity.trim().equals("even")) { join(friendsAndEnemies[0], Term.start - 1, Term.end); } else { int eneymyAncestor1 = findAncestor(friendsAndEnemies[0], Term.start - 1); int eneymyAncestor2 = findAncestor(friendsAndEnemies[0], Term.end); if (friendsAndEnemies[1][Term.start - 1] == -1 && friendsAndEnemies[1][Term.end] == -1) { friendsAndEnemies[1][Term.start - 1] = eneymyAncestor2; friendsAndEnemies[1][Term.end] = eneymyAncestor1; } else if (friendsAndEnemies[1][Term.start - 1] != -1 && friendsAndEnemies[1][Term.end] == -1) { join(friendsAndEnemies[0], friendsAndEnemies[1][Term.start - 1], Term.end); friendsAndEnemies[1][Term.end] = eneymyAncestor1; } else if (friendsAndEnemies[1][Term.start - 1] == -1 && friendsAndEnemies[1][Term.end] != -1) { join(friendsAndEnemies[0], friendsAndEnemies[1][Term.end], Term.start - 1); friendsAndEnemies[1][Term.start - 1] = eneymyAncestor2; } else { join(friendsAndEnemies[0], friendsAndEnemies[1][Term.end], Term.start - 1); join(friendsAndEnemies[0], friendsAndEnemies[1][Term.start - 1], Term.end); } } int pause = check(friendsAndEnemies); if (pause == friendsAndEnemies[0].length) { continue; } else { break; } } System.out.println(counter - 1); for (int i = counter + 1; i <= conditions; i++) { int x = in.nextInt(); int y = in.nextInt(); String z = in.nextLine(); } length = in.nextInt(); } } private static int findAncestor(int[] friends, int value) { int r = value; while (r != friends[r]) { r = friends[r]; } return r; } private static void join(int[] pre, int x, int y) { int ancestorX = findAncestor(pre, x); int ancestorY = findAncestor(pre, y); int r = y; if (ancestorX != ancestorY) { while (r != pre[r]) { int temp = pre[r]; pre[r] = ancestorX; r = temp; } pre[ancestorY] = ancestorX; } } private static int check(int[][] friendsAndEnemies) { int i = 1; for (; i < friendsAndEnemies[0].length; i++) { int friendAncestor = findAncestor(friendsAndEnemies[0], friendsAndEnemies[0][i]); int enemyAncestor = -1; if (friendsAndEnemies[1][i] != -1) { enemyAncestor = findAncestor(friendsAndEnemies[0], friendsAndEnemies[1][i]); } if (friendAncestor == enemyAncestor) { break; } else { continue; } } return i; } } class Term { public static int start; public static int end; public static String parity; } | Runtime Error 1003 Parity | Sunny | 1003. Чётность | 8 фев 2015 09:10 | 1 | Deleting this post... had to hack another solution. Still don't see what was wrong with the original approach... must have been some kind of parsing issue with the input. Edited by author 08.02.2015 09:36 | Runtime error (access violation) | shadowElkorchi | 1003. Чётность | 23 мар 2014 07:58 | 3 | I don't understand why it show me a Runtime error (access violation) when it s compiling and it works perfectly in my computer ??? Can you share your code please? There can be many reasons for this behavior. Try to define a bigger array! | Страница 3 | read the problem carefully | lantimilan | 1003. Чётность | 20 янв 2013 04:06 | 1 | The input is of multiple testcases, and each testcase starts with N, the length of the sequence, and K, the number of pairs of intervals. You only know when you stop after got N == -1. Naive ideas will get TLE even for testcase #1, and you will see your code runs out of 2s limit when feeding a testcase with N=10^9 and K=5000, when all pairs are good and you should output 5000. | The test case! | earthworm | 1003. Чётность | 3 янв 2013 06:35 | 1 | | Who can help me?WA#1 | hywwqq | 1003. Чётность | 20 ноя 2012 17:52 | 1 | #include <iostream> #include <cstdio> #include <deque> #include <map> #include <string> #include <cstring> #include <cstdlib> #include <algorithm> #include <functional> using namespace std; const int maxn=20002; int Hlen=6000; int father[maxn]; int flag[maxn]; int getfather(int x) { int tmp=father[x]; if(x==father[x]) return x; else { father[x]=getfather(father[x]); return father[x]; } } void Union(int x,int y) { int fx=getfather(x); int fy=getfather(y); if(fx!=fy) father[fy]=fx; } void init() { for(int i=0;i<maxn;i++) father[i]=i; } int mp(int x) { int ax=x%Hlen; if(flag[ax]!=-1&&flag[ax]!=x) ax=(ax+1)%Hlen; flag[ax]=x; return ax; } int main() { int len,N,i; int level=10000; while(1) { scanf("%d",&len); if(len==-1) break; scanf("%d",&N);
init(); memset(flag,-1,sizeof (flag)); for(i=0;i<N;i++) { int a,b; char str[10]; scanf("%d%d%s",&a,&b,str); a=mp(a-1); b=mp(b); if(str[0]=='e') { if(getfather(a)==getfather(b+level)) break; Union(a,b); Union(a+level,b+level); } else { if(getfather(a)==getfather(b)) break; Union(a,b+level); Union(a+level,b); } } char str1[100]; int m=i; for(i;i<N;i++) gets(str1); printf("%d\n",m); } system("pause"); return 0; } | i want to know whether there exits this data? | yejinru | 1003. Чётность | 22 янв 2019 11:08 | 3 | 10 6 1 2 even 1 1 even 3 4 odd 5 6 even 1 6 even 7 10 odd i think the answer of this data should be 1,but my program answer is 4 but it return an accepted! why?i think 4 is correct. "1 2 even" -> first 2 digits are 00 or 11 "1 1 even" -> first digit is 0. So if first 2 digits are 00, everything is ok | Why is it 201? | thefourtheye | 1003. Чётность | 21 мар 2012 23:52 | 1 | | #1 TLE whats wrong? Java code | Sammael | 1003. Чётность | 9 мар 2012 05:19 | 1 | My program passed tests posted below but i got TLE in #1 test. I really don't know what is wrong with it. Could someone help me by telling me what is wrong or giving me some test? I would be very grateful. TESTS: 100 5 5 6 odd 7 8 odd 1 6 even 1 4 odd 7 8 even 3 3 1 1 odd 3 3 odd 1 3 odd 5 4 1 2 even 4 5 even 1 5 odd 3 3 even 10 5 1 2 even 3 4 odd 5 6 even 1 6 even 7 10 odd 20 8 1 9 odd 10 17 odd 18 26 odd 4 5 odd 27 40 even 21 40 odd 1 20 odd 10 20 odd 200 8 1 9 odd 10 17 odd 18 26 odd 4 5 odd 27 40 even 21 40 odd 1 20 odd 10 20 odd -1 ANSWERS: 4 3 3 3 2 6 MY CODE: import java.util.HashMap; import java.util.List; import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); Main test = new Main(); List<Integer> results = new ArrayList<Integer>(); // LOADING DATA while (true) { int length = input.nextInt(); input.nextLine(); if (length == -1) { break; } else { int hintCounter = input.nextInt(); input.nextLine(); // IF THERE IS NO ANSWER - CONTINUE if (hintCounter == 0) { results.add(0); continue; } List<Row> testData = new ArrayList<Row>(); // READ ANSWERS for (int i = 0; i < hintCounter; i++) { int start = input.nextInt(); int end = input.nextInt(); String parity = input.nextLine().trim(); Row newRow = test.new Row(start, end, (parity.equals("odd")) ? true : false); testData.add(newRow); } Database db = test.new Database(length); int correctHints = 0;
// ADD ANSWERS TO DATABASE AND CHECK AUTHENTICITY for (int i = 0; i < testData.size(); i++) { Row r = testData.get(i); db.addElement(r.start, r.end, r.odd); if (db.isConsistent()) { correctHints++; } else { break; } } results.add(correctHints); } } // PRINT RESULTS for (int i = 0; i < results.size(); i++) { System.out.println(results.get(i)); } } private class Row { int start; int end; Boolean odd; public Row(int pStart, int pEnd, Boolean pOdd) { start = pStart; end = pEnd; odd = pOdd; } } private class Database { HashMap<Integer, HashMap<Integer, Boolean>> data; Boolean consistent; int maxLength; int maxX; int maxY; int minX; int minY; public Database(int pMaxLength) { data = new HashMap<Integer, HashMap<Integer, Boolean>>(); consistent = true; maxX = 0; maxY = 0; minX = 2000000000; minY = 2000000000; maxLength = pMaxLength; } public Boolean isConsistent() { return consistent; } public void addElement(int x, int y, Boolean odd) { consistent = ((x < 1 || y > maxLength) ? false : true);
if (consistent) { if (data.containsKey(x)) { // X ALREADY EXISTS if (data.get(x).containsKey(y)) { // Y ALSO EXISTS consistent = (data.get(x).get(y).equals(odd) ? true : false); return; } else { // Y NOT EXISTS maxY = (y > maxY ? y : maxY); minY = (y < minY ? y : minY); data.get(x).put(y, odd); } } else { // X NOT EXISTS maxX = (x > maxX ? x : maxX); minX = (x < minX ? x : minX); data.put(x, new HashMap<Integer, Boolean>()); data.get(x).put(y, odd); } // UPDATING THE DATA updatePefixes(x, y, odd); updateSuffixes(x, y, odd); } else { // DO NOTHING } } public void updatePefixes(int x, int y, Boolean odd) { // UPDATING PREFIXES for (int i = minX; i < x; i++) {
if (data.containsKey(i) && data.get(i).containsKey(x - 1)) { Boolean leftOdd = data.get(i).get(x - 1) ^ odd; addElement(i, y, leftOdd);
for (int j = y + 1; j <= maxY; j++) { if (data.containsKey(y + 1) && data.get(y + 1).containsKey(j)) { addElement(i, j, leftOdd ^ data.get(y + 1).get(j)); } else { // DO NOTHING } } } else { // DO NOTHING } } } public void updateSuffixes(int x, int y, Boolean odd) { // UPDATING SUFFIXES for (int i = y + 1; i <= maxY; i++) { if (data.containsKey(y + 1) && data.get(y + 1).containsKey(i)) { addElement(x, i, odd ^ data.get(y + 1).get(i)); } else { // DO NOTHING } } } } } | What's the idea ??? HELP~~ | vongang | 1003. Чётность | 21 ноя 2011 20:03 | 1 | | How it can be solved with disjoint sets??? | Enigma [UB of TUIT] | 1003. Чётность | 19 сен 2023 21:37 | 3 | How it can be solved with disjoint sets? Anybody help me please. This is my mail: quvondiq.otajonov.tuit@gmail.com. I'll wait for answer! Thanks for advance!!! I know it's an old thread, but it's how I solved it. So spoilers and all. if l->r is even, then s[r] and s[l - 1] have the same parity (where s[x] is the partial sum of bits from 1 to x) if l->r is odd, then they have opposite parities We add l-1 and r to a dsu. So a dsu is just a tree of all dependencies, no matter if odd or even (see how I differentiate between the two below). I used dsu with an added property that is only available for dsu roots: sons[root][0] is the "representative" of all elements that have the same parity of root, sons[root][1] is the "representative" of all elements that have opposite parity of root. Anything else besides the root->representative edges will only have 0s, codifying that entire subtrees have the same parity. So first off when you do find, I haven't really bothered with path compression. And instead of just saying what is the dsu root for a node, you also say which side it came from (0 if it came from sons[root][0] and 1 for sons[root][1]) - so (0, root) means it has the same parity as root and (1, root) means it has opposite parities. So now when you do union, you first have a small case, if the two nodes are already in a tree, you have to verify that the sides they're on match the parity of s[r] - s[l - 1] otherwise you stop at the current test. Now, if they're not yet united, you have 4 cases that are basically just 2: if l-1 and r are on the same side of their respective dsus with s[r]-s[l-1] even, then this is one case if l-1 and r are on opposite sides of their respective dsus with s[r]-s[l-1] odd, then this is one case(identical with the previous one) And of course you have the opposite cases as well, which form another case you have to treat separately. So now you just have to move the left and right sides from one tree to the other so that they all match up correctly. You can do this however you like, just make sure that the property we've added to the dsu (sons is a unique property of the root of a dsu) is kept. Here's how I did it (let's treat just the case where l->r is even and l-1 and r are on the 0 sides of their respective dsus), and let's say l - 1 has root T1 and r root T2, we want to join the tree T2 into tree T1. T1 T2 0/ \1 0/ \1 a b c d | | | | A B C D (l - 1 comes from A, r comes from C) a, b, c, d are representatives of A, B, C, D. And this is how the finalized tree will Look:
T1 0/ \1 T2 d 0|\0 |\ a c D b | | | A C B As you can see, since T2 is no longer a root, sons[T2] becomes redundant since it's gonna have 0's on the edges which is what keeps the property. For the opposite case, you do something similar, just that T2 will be on the 1 side of T1 and you play around with the representatives. Of course there are some cases where some roots don't yet have both/any sons, but it's not too ugly to deal with them. Also for implementation, I normalized values but I think you could just use unordered_map/map. | HINT TEST #1 | Qafqaz Sehriyar Novruzov | 1003. Чётность | 17 июн 2011 05:05 | 1 | if you are get wrong answer #1 or time limit #1 , probably your bug is that,you don't read input to end..I was get time limit #1..Because I didn't read input to end..when I find correct answer I break..then I found my bug and I read input to end..finally I got AC..If you don't read input to end , probably , your bug is that..you must read input to end.. Edited by author 17.06.2011 05:11 | tests cases | Alexander J. Villalba G. | 1003. Чётность | 25 апр 2011 02:53 | 2 | 2, 2 even is impossible? there are those cases? 2, 3 even implies that the sequence of binary numbers is 11 between 2 and 3? in a sequence of binary digits as 000, there is not an even number of 1's or an odd number of 1's. But it was always supposed to be even or odd ... But zero is not even or odd ??? |
Страницы: 4 3 2 1 Предыдущая |
|