delete iostream and using namespace std. all cin cout replace on scanf and pritf write in start of code: #define CRT_SECURE_NO_WARNINGS and #include<cstdio> and behind your vectors,pair and queue write std:: do vector WITHOUT ANY INTS, ALL BOOL DONT USE PUSH_BACK its really slow, just write size of vector Example: >std::vector<std::vector<bool>> a(n); >std::vector<bool> b(m); and call with a[i][j] or something else; If you look at other aspects of the task, then EASY BFS Or array of vector <bool>. It uses less memory too. Is it really needed to set 4mb memory limit? I really must to remember pascal for this task, because the same solution have TL (not a Scanner) or ML on java. May be it's possible to up memory limit to 8mb? #include <stdio.h> #include <iostream> using namespace std; int n, m, segRez[3004]; int segm1[3004]; char segm2[6005]; int main() { cin >> n >> m; for(int i = 0; i < n; ++i){ gets_s(segm2); for(int j = 0; j < m; ++j){ segRez[j] = segm1[j] + int(segm2[j<<1] - 48); segm1[j] = int(segm2[j<<1] - 48); if(j - 1 >= 0 && ((segRez[j - 1]|segRez[j])) == 3){ cout << "No"; return 0; } } } cout << "Yes"; } GC.Collect(); on each iteration has helped why my O(N * M) solution works for 2.65 seconds? I think 9 * 10^6 operstions should be done faster... Because reading 3000 x 3000 integers takes a lot of time. Just a passing note: the same exact code gets TLE in G++ but AC in Visual C++ (with a very comfortable margin). Make sure to test your code in both compilers before making a judgement that your code is too slow, for those who are coding in C/C++. That's ridiculous for some reason. TLE in G++ but AC in Visual C++ without a single edit in the source code. wow, the same one problem У меня получилось вот что I have this: > http://ideone.com/8CHWDd Почему проверка считает что ответ неверен Why it's wrong? 1 1 0 ==== Yes 1 1 1 ==== Yes 3 1 1 1 0 ==== Yes 3 1 0 0 0 ==== Yes 2 2 0 0 0 0 ==== Yes 2 2 1 0 0 1 ==== Yes 3 3 1 1 1 1 0 1 1 1 1 ==== No 3 3 1 1 1 1 1 1 1 1 1 ==== Yes 3 3 1 0 1 0 1 0 1 0 1 ==== Yes 4 2 1 1 0 0 0 0 1 1 ==== Yes 4 2 1 1 1 0 0 1 1 1 ==== No 4 4 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 ==== Yes 4 4 1 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 ==== Yes 4 4 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 ==== Yes 4 2 1 1 0 1 1 1 1 1 ==== No 3 3 1 1 1 1 0 1 1 1 1 Yes / No ? Can't solve this problem fast? I can give a little hint: Think about role of squares like 01 11 or 10 11 or 11 01 and finally 11 10 Thats all. Good luck! Edited by author 02.06.2005 03:45 thank you for this advice! fantastic Yeah, much better than doing DFS's and checking... { ACCEPTED !!!!!!!!!! } Var S : Array [0..1,1..3000] of Byte; N,M,I,J,C : Longint; Begin {} Read(M,N); { <-- Read(N,M); !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! } C := 1; For J:=1 to N do S[1-C,J] := 0; { Обнуляем "предыдущую" строку } For I:=1 to M do { Цикл по всем строкам } Begin For J:=1 to N do Read(S[C,J]); { Читаем новую строку } For J:=1 to N-1 do { Ищем неприятности ;) } If (((S[1-C,J]=0) and (S[1-C,J+1]=1) and (S[C,J]=1) and (S [C,J+1]=1)) or ((S[1-C,J]=1) and (S[1-C,J+1]=0) and (S[C,J]=1) and (S [C,J+1]=1)) or ((S[1-C,J]=1) and (S[1-C,J+1]=1) and (S[C,J]=0) and (S [C,J+1]=1)) or ((S[1-C,J]=1) and (S[1-C,J+1]=1) and (S[C,J]=1) and (S [C,J+1]=0))) then Begin Writeln('No'); Halt; End; C := 1 - C; End; Writeln('Yes'); End. My prog uses only private static byte[] mat;// max 3000 * 1 byte private static boolean ok;// 1 byte private static byte x, y; // 2 byte private static int n, m, i, j; // 4*4 byte=16 byte field variables its memory cant be 5 510 KB. total memory is 3019 B. I cant understand why i'm getting memory limit on test6 Try to read input strings this way: BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); ......... char[] input_str = new char[2 * m + 2]; ......... in.read(input_str, 0, 2 * m + 1); It help me to get AC with 0.296 sec. and 1662КБ. Good Luck! Edited by author 23.09.2009 17:08 Edited by author 23.09.2009 17:08 Thanks a lot. I got AC by your help Edited by author 09.08.2009 23:36 #include<iostream> using namespace std; int main () { int a[3000],b[3000],c[3000]; long long int i,j,k,n,m; cin>>n>>m; for (i=0;i<n;i++){ cin>>a[i]; for(j=0;j<m;j++){ cin>>a[j]; } { c[j]= a[j] + b[j]; } for (j=0;j<m-1;j++){ if ((c[j] = 1) && (c[j+1] = 2) || (c[j] = 2) && (c[j+1] >= 1)) { cout<<"NO";
return 0; } else { cout<<"YES";} } } return 0; } See my 0.046 s source. Please, write letter to timus_support(at)acm.timus.ru and explain why tests in this problem are bad. Please give me some tests. now i have AC. it was very stupid bag..... Edited by author 13.03.2008 16:25 |
|