|
|
Show all threads Hide all threads Show all messages Hide all messages | TLE with G++ 4.9, AC with Visual C++ 2013 | zlo | 1737. Mnemonics and Palindromes 3 | 26 Jul 2017 17:17 | 2 | For some reason I get TLE with G++ 4.9 and AC with Visual C++ 2013 with exactly the same code. I tried to use scanf/printf instead of cin/cout, but had no difference. On my machine this code works <100ms for every n with G++. Can anyone explain why I get TLE with G++? Thanks! #include <string> #include <queue> #include <iostream> using namespace std; int main() { int n; cin >> n; queue<string> result; result.push("a"); result.push("b"); result.push("c"); char abc[] = {'a', 'b', 'c'}; for (int i = 1; i < n; i++) { while (true) { string &s = result.front(); if (s.size() > i) { break; } char last = s[s.size() - 1]; if (s.size() > 1) { char lbo = s[s.size() - 2]; for (int k = 0; k < 3; k++) { char c = abc[k]; if (last != c && lbo != c) { result.push(s + c); } } } else { for (int k = 0; k < 3; k++) { char c = abc[k]; if (last != c) { result.push(s + c); } } } result.pop(); } if ((i + 1) * result.size() > 100000) { cout << "TOO LONG"; return 0; } } while (!result.empty()) { cout << result.front() << endl; result.pop(); } return 0; } Because s+c is a temporary object You are creating temporary objects and throwing them away O(N) times Looks like G++ failed to notice that it is unnecessary to create and destroy objects And MSVC noticed that and replaced with something more effective | WA4 | Serebryakov Dmitry (NNSU) | 1737. Mnemonics and Palindromes 3 | 22 Jul 2017 17:55 | 2 | WA4 Serebryakov Dmitry (NNSU) 16 Nov 2009 19:48 Don't forget about case n=1 answer: a b c Re: WA4 Mahilewets 22 Jul 2017 17:55 | It`s absolutely amazing problem! | I_love_alyona | 1737. Mnemonics and Palindromes 3 | 14 Aug 2013 15:16 | 1 | | wa #8 helppppppp pls | h1ci | 1737. Mnemonics and Palindromes 3 | 4 Apr 2010 18:47 | 5 | whats test 8 or whats wrong with that: #include<iostream> using namespace std; int main() { int n; cin >> n; char a[3]={'a','b','c'}; if(n*6>10000){ cout<<"TOO LONG" << endl; return 0;} if(n==1){ cout << "a\nb\nc\n"; return 0;} for(int i=0; i<n; i++) { cout << a[i%3]; } cout << endl; a[0]='a'; a[1]='c'; a[2]='b'; ////////////////////////////// for(int i=0; i<n; i++) { cout << a[i%3]; } cout << endl; a[0]='b'; a[1]='a'; a[2]='c'; ////////////////////////////// for(int i=0; i<n; i++) { cout << a[i%3]; } cout << endl; a[0]='b'; a[1]='c'; a[2]='a'; ////////////////////////////// for(int i=0; i<n; i++) { cout << a[i%3]; } cout << endl; a[0]='c'; a[1]='a'; a[2]='b'; ////////////////////////////// for(int i=0; i<n; i++) { cout << a[i%3]; } cout << endl; a[0]='c'; a[1]='b'; a[2]='a'; ////////////////////////////// for(int i=0; i<n; i++) { cout << a[i%3]; } cout << endl; return 0; } Your problem is that line - if(n*6>10000){ cout<<"TOO LONG" << endl; return 0;} } whats wrong with that? If the output exceeds 10000 letters output "TOO LONG" ?!?! Oh, sorry my bad it's 100 000 not 10 000; AC now Edited by author 25.11.2009 16:33 Edited by author 25.11.2009 16:33 Edited by author 25.11.2009 16:33 Edited by author 25.11.2009 16:33 Edited by author 25.11.2009 16:33 Btw, instead of copy/pasting code for every permutation you can char a[] = "abc"; do{ F(i,n) cout << a[i%3]; cout << endl; }while(next_permutation(a,a+3)); where F is #define F(i,n) for(int i = 0; i < n; ++i) | why wa2???? | Prosto Misha | 1737. Mnemonics and Palindromes 3 | 17 Nov 2009 11:44 | 4 | Какой может быть 2 тест. n = 1? Если так то доблжен быть ответ в 3 строчки? a b c? Да насколько я знаю это тест под номером 4 так как только так WA 4 получал и потом как исправил свой код и получил AC и еще каков будет ответ на тест n = 16667 ? Edited by author 01.11.2009 19:22 Grumpy input 16667 output TOO LONG Edited by author 01.11.2009 23:18 I think n=3. I had mistake "bcc" (right "bca"). I got WA2. | Test #3 | Maxim Dvoynishnikov (Dnipropetrovsk NU) | 1737. Mnemonics and Palindromes 3 | 1 Nov 2009 21:34 | 5 | Test #3 Maxim Dvoynishnikov (Dnipropetrovsk NU) 1 Nov 2009 17:58 if length of output<100000 for all test result 6 lines ;) special test n=1 and don't forget: The names should be given in the alphabetical order Edited by author 01.11.2009 18:26 Re: Test #3 Maxim Dvoynishnikov (Dnipropetrovsk NU) 1 Nov 2009 19:10 if length of output<100000 for all test result 6 lines ;) I think it isn't correct. n = 4 abc a acb a bac b bca b cab c cba c i think you can do it PS.Don't output space it's just hint for you Edited by author 01.11.2009 19:32 Re: Test #3 Maxim Dvoynishnikov (Dnipropetrovsk NU) 1 Nov 2009 21:34 I misunderstood word "substring"... Thanks. |
|
|
|