Show all threads Hide all threads Show all messages Hide all messages |
HINT | Wonsei | 1654. Cipher Message | 6 Feb 2021 20:27 | 3 |
HINT Wonsei 15 Sep 2020 19:52 Use stacks. Push one letter by letter. If stack.top() == current letter, pop the stack. else push the letter in the stack. Re: HINT Lifeisbeautiful 6 Jan 2021 10:19 Re: HINT Eusebiu_distrugatorul 6 Feb 2021 20:27 |
Code not producing any output? | Naman Sharma | 1654. Cipher Message | 20 May 2020 13:21 | 2 |
#include<bits/stdc++.h> using namespace std; stack<char> S; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); string s; cin >> s; int len = s.length(); for(int i = 0; i < len;i++) { char c; if(S.empty()) c = 0; else c = S.top(); if(c == s[i]) S.pop(); else S.push(c); } string ans = ""; len = S.size(); for(int i = 0; i < len;i++) { char c = S.top(); ans += c; S.pop(); } reverse(ans.begin(),ans.end()); cout << ans; } You should do S.push(s[i]) in your else clause inside the for loop. |
Stuck on Test 6? Read Here! | Davanish | 1654. Cipher Message | 8 Apr 2020 23:22 | 6 |
For Time limit exceeded: If you get time limit exceeded, it must mean that you're trying to modify the input string (i.e. trying to delete i-th chars). Try creating a new OUTPUT string without modifying the INPUT string. Note: if you're using a high language such as java or C#, try using the StringBuilder object to build your output string. For Wrong Answer(WA): If you get WA, try some of these test cases: Input: "dddd" Output: "" Input: "ddddd" Output: "d" Input: "abba" Output: "" Input: "abbbbac" Output: "c" Input: "wliisddsmmleeddw" Output: "" Input: "avcbbffcv" Output: "a" Hope this helps. Edited by author 12.07.2012 00:47 Input: "abbbbac" Output: "c" Спасибо, помогло! For Time limit exceeded: If you get time limit exceeded, it must mean that you're trying to modify the input string (i.e. trying to delete i-th chars). Try creating a new OUTPUT string without modifying the INPUT string. Note: if you're using a high language such as java or C#, try using the StringBuilder object to build your output string. For Wrong Answer(WA): If you get WA, try some of these test cases: Input: "dddd" Output: "" Input: "ddddd" Output: "d" Input: "abba" Output: "" Input: "abbbbac" Output: "c" Input: "wliisddsmmleeddw" Output: "" Input: "avcbbffcv" Output: "a" Hope this helps. Edited by author 12.07.2012 00:47 Thanks a lot...I could'n understand the problem statement first, now, reading ur comment I clearly understood the problem. for me problem was that program was returning "axx" on "aaaxx" Edited by author 18.03.2017 19:56 |
ac 0.015 | Dyryaev Daniil | 1654. Cipher Message | 30 Oct 2019 15:05 | 1 |
ac 0.015 Dyryaev Daniil 30 Oct 2019 15:05 #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cmath> #include <algorithm> #include <set> #include <vector> #include <string> #include <cstdlib> using namespace std; void optimization() { cin.tie(nullptr); ios_base::sync_with_stdio(false); } int main() { optimization(); string s; int k = -1; cin >> s; char c[200000]; for (char & i : c) { i = ' '; } for (char i : s) { if (k > -1) { if (c[k] == i) { c[k] = ' '; k--; } else { k++; c[k] = i; continue; } } else { k++; c[k] = i; } } for (char i : c) { if (i != ' ') { cout << i; } } return 0; } |
AC C++ | soroush | 1654. Cipher Message | 12 Aug 2019 12:27 | 1 |
AC C++ soroush 12 Aug 2019 12:27 #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MAX = 1e5+10; const ll ZERO = 0; #define endl '\n' #define dokme(x) cout << x ; return(0); #define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); stack < char > stk; int main(){ migmig; stk.push('.'); char c[200001]; cin >> c; int n=strlen(c); for (int i =0; i < n ; i ++ ){ if (stk.top()!=c[i]){ stk.push(c[i]); } else{ stk.pop(); } } n=stk.size()-1; memset(c,0,sizeof(c)); for (int i = 0 ; i<n ; i ++ ){ c[n-i-1]=stk.top(); stk.pop(); } cout << c; } |
Tle in 6? Look at source code. | Cebiyev_Ferhad_Qafqaz U. | 1654. Cipher Message | 12 Jul 2019 20:08 | 4 |
#include <iostream> #include <cstdlib> #include <deque> using namespace std; int main() { int h; char s[200001]; scanf("%s", &s); int n=strlen(s); deque<char> v (s, s + n );
if(v.size()==2 && v[0]==v[1] ) return 0; b: h=2; for(int i=0; i<v.size()-1 ;i++) if(v[i] == v[i+1]) { v.erase(v.begin() + i); v.erase(v.begin() + i); h=1; } if(h==1) goto b;
for(int i=0; i<v.size(); i++) cout << v[i];
return 0; } Hello, If you are still working on this, let you know that it can't be solved with erase. I implemented a similar algorithm in Java which goes through the string and deletes the successful characters and it also got TLE on test 6.The easiest way is removing the successful characters as you read them. nc->new character from the input. if(i!=-1&&c[i]==nc){//new char is equal to the char at the end of the string, remove it i--; }else{ //add the new char to the string i++; c[i]=nc; } Hope this helps You got TLE because deque has poor deletion performance on positions other than the front and back. |
0.109s answer | dula | 1654. Cipher Message | 12 Jun 2019 11:39 | 6 |
#include<iostream> #include<string.h> #include<deque> #include<stdio.h> using namespace std; int main() { string node; cin >> node; int one,two; one = 0; two = 1; int pre = 0; for(int i = 0;i < node.size();i++) { if(node[i] == '!') continue; if(node[i] == node[i+1]) { node[i] = node[i+1] = '!'; one = pre; if(i+2 < node.size()) two = i+2; while(one> 0 && two < node.size()) { while(one > 0 && node[one] == '!') one--; if(node[one] == node[two] ) { node[one] = node[two] = '!'; one--;two++; } else break; } } else pre = i; }
for(int i = 0;i < node.size();i++) { if(node[i] != '!') cout << node[i]; }
} I use stack and my solution works 0.064s :) My solution works 0.048s ;) Why your solutions is right? if input is: sddssdds then your ans is "ss"! |
If you have WA #3 | german_goncharov | 1654. Cipher Message | 2 Apr 2019 03:53 | 1 |
For test you can use this string: hkjgnnngkikipipekkfkfgg Correct result is: hkjgngkikipipefkf |
how to make faster? | TSU_TheScull | 1654. Cipher Message | 2 Apr 2019 03:05 | 1 |
using System; namespace pain { class Program { static void Main(string[] args) { string s = Console.ReadLine(); char[] ss = new char[s.Length]; for (int i = 0; i < s.Length; i++) ss[i] = s[i]; for (int i = 0; i < s.Length - 1;) { if (ss[i] == ss[i + 1]) { if (i - 1 >= 0) { int n = i + 2; b: if (n <= s.Length - 1) { if (ss[n] != ' ') { ss[i] = ss[n]; ss[n] = ' '; ss[i + 1] = ' '; } else { n++; goto b; } } else break; } else { ss[i] = ' '; ss[i + 1] = ' '; } if (i >= 1) i--; else i++; } else i++; } for (int i = 0; i < s.Length; i++) if(ss[i] != ' ') Console.Write(ss[i]); //Console.Write(st2(s)); Console.ReadLine(); } public static string st1(string s, ref int n) { if (s.Length - 1 > n) { if (s[n] == s[n + 1]) { s = s.Remove(n, 2); if (n >= 2) n -= 2; else n--; } n++; s = st1(s, ref n); } return s; } public static string st2(string s) { for (int i = 0; i < s.Length - 1; i++) { if (s[i] == s[i + 1]) { s = s.Remove(i, 2); if (i >= 2) i -= 2; } } return s; } public static string st3(string s) { int n = 0; int nt = s.Length - 1; string[] ss = new string[nt]; for (int i = 0; i < nt; i++) { bool d = false; for (int j = i; j < nt; j++) { if (ss[i] == s[j].ToString()) { d = true; } } if (!d) { ss[n] = s[i].ToString(); n++; } } n = 0; while (nt != 0) { nt = s.Length; for (int i = 0; i < ss.Length; i++) { s = s.Replace(ss[i] + ss[i], ""); } if (nt == s.Length) break; } return s; } } } Edited by author 02.04.2019 03:06 |
WA2 | DenisBordachkov | 1654. Cipher Message | 15 Feb 2019 02:29 | 1 |
WA2 DenisBordachkov 15 Feb 2019 02:29 Why Wring answer? import java.util.Scanner; public class T1654 { public static char[] arr; public static String out = ""; public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); String inp = sc.next(); sc.close(); arr = new char[inp.length()]; arr = inp.toCharArray(); format(); if(out != "") { System.out.println(out); } else { System.out.println(""); }
}
public static void format() { boolean isFormat = false; int l = arr.length; for(int i = 0; i< l-1; i++) { if(arr[i] == arr[i+1]) { arr[i] = 0; arr[i+1] = 0; isFormat = true; } else if(arr[i] != arr[i+1] & arr[i] != 0){ out += arr[i]; } } out+= arr[arr.length-1]; if(isFormat == true) { arr = new char[out.length()]; arr = out.toCharArray(); out = ""; format(); } } } |
A simple python script to generate long test cases | Xitsa | 1654. Cipher Message | 27 Nov 2018 09:08 | 1 |
import random letters = ['a' ,'b' ,'c' ,'d' ,'e' ,'f' ,'g' ,'h' ,'i' ,'j' ,'k' ,'l' ,'m' ,'n' ,'o' ,'p' ,'q' ,'r' ,'s' ,'t' ,'u' ,'v' ,'w' ,'x' ,'y' ,'z'] example = 'xitsa' while len(example) < 199999: letter = random.choice(letters) point = random.randrange(0, len(example)) example = example[:point] + letter + letter + example[point:] print(example) |
why stack so long | IlushaMax | 1654. Cipher Message | 1 Oct 2018 13:38 | 2 |
I thought that stack is the best thing in this case but I've seen 0.015 and 0.001 sec . I've got 0.046 Maybe it's because of the choice of language. I use C++17 and it run in 0.001s |
little asvice (no spoilers) | bstu_student | 1654. Cipher Message | 9 Aug 2018 09:09 | 1 |
char[200001] gives perfect time if you will check repeats while string is inputting |
use printf() instead of cout and string instead of char if you use c++ stl | Haloom | 1654. Cipher Message | 9 Aug 2018 09:08 | 2 |
i used deque. cout got me TLE.using printf save me. if(st.front()!=s[i]) { st.emplace_front(s[i]); } else st.pop_front();
for(it=st.end()-1; it>=st.begin(); it--) { printf("%c",*it); } i say more - it's better don't use stl-containers if it's possible. char[200001] gives perfect time |
Time limit exceeded on tes 8 (java), i dont know which way is excellent | Aydar | 1654. Cipher Message | 21 Mar 2018 06:11 | 4 |
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Iterator; import java.util.Stack; public class problem1654 { public static void main(String[] args) throws IOException { BufferedReader inp = new BufferedReader(new InputStreamReader(System.in)); String str=inp.readLine(); Stack<Character> st=new Stack<Character>(); st.push(str.charAt(0)); String s=""; for(int i=1;i<str.length();i++){ if(!st.empty()&&st.peek()==str.charAt(i)) st.pop(); else{ st.push(str.charAt(i));
} }
while(!st.empty()){ s=s+st.pop(); } int n=s.length(); for(int i=0;i<n;i++){ System.out.print(s.charAt(n-i-1));
} }} When i used stack(from STL) in C++, i'd got TL8. But after i realzed stack by using array, i got AC your reply help me very much!3Q Don't use : while(!st.empty()){ s=s+st.pop(); } -------- Use this phrase at the end of your Code: Iterator<Character> b = st.iterator(); while(b.hasNext()){ System.out.print(b.next()); } |
wh Test 3 | Mr.Creative | 1654. Cipher Message | 10 Jan 2018 15:20 | 1 |
// Harry Poter #include <stdio.h> #include <iostream> #include <stdlib.h> #include <string.h> using namespace std; int main() { char line[200001], w2[200001]; cin.getline(line, sizeof(line)); int t = 0, i; for(i = 0; i < strlen(line); i++){ if (line[i] == line[i + 1]) { i++; A: if (line[i + 1] != line[i + 2]) { if (t != 0 && w2[t - 1] == line[i + 1]) {t--; i += 1; goto A;} } } else {w2[t++] = line[i];} } w2[t] = '\0'; printf("%s", w2); } |
For those who have WA#4 | Sandu Petrasco | 1654. Cipher Message | 29 Aug 2016 12:07 | 2 |
The test is "abcdeedcbaabcdeedcba"(without quotes). The answer should be ""(empty string). hey mi anwser code is the same, what is the bug |
wa #4 | gerson | 1654. Cipher Message | 29 Aug 2016 12:00 | 1 |
wa #4 gerson 29 Aug 2016 12:00 hey if one else to know print the anser plese say me..in the test #4 i have a empty string, but the judge say me "wa" in test #4.... why??? help me please. #include <bits/stdc++.h> using namespace std; int main(){ string cad,res; cin>>cad; res = ""; int tam = cad.length(); int i,j; i=0; j=1; int boolean[tam]={0}; while(j<tam){ if(cad[i]==cad[j]){ boolean[i] = 1; boolean[j] = 1; if(i-1>=0){ i-=1; j+=1; }else{ i=j+1; j+=2; } }else{ i=j; j+=1; } } for(int i=0;i<tam;i++){ if(boolean[i]==0) res+=cad[i]; } cout<<res; return 0; } |
WA#5 | Dewesh Deo Singh | 1654. Cipher Message | 25 Dec 2015 13:34 | 3 |
WA#5 Dewesh Deo Singh 19 Dec 2015 12:45 Can any body tell me whai is in the test case 5...??? My code seems right but everytime it says WA#5... 200000 char in test case #5!! Re: WA#5 Dewesh Deo Singh 25 Dec 2015 13:34 Thanksss.. It helped me a lot... Edited by author 25.12.2015 13:35 |
I'm trying to use stack. It's true ! Why ? | TruongNT | 1654. Cipher Message | 22 Dec 2015 07:45 | 1 |
import java.util.Scanner; import java.util.Stack; public class CliperMessage_1654_Stack { public static void main(String[] arg1) { Scanner sc=new Scanner(System.in); StringBuilder sb=new StringBuilder(); Stack<Character> stc=new Stack<>(); sb.append(sc.nextLine()); if(sb.length()<=200000){ for(int i=0;i<sb.length();i++){ if(stc.isEmpty()||(stc.peek()!=sb.charAt(i))) stc.push(sb.charAt(i)); else if((stc.peek()==sb.charAt(i))) stc.pop();
}
StringBuilder sbn=new StringBuilder(); int j=0; while(!stc.empty()) sbn.insert(j++, ""+stc.pop()); System.out.println(sbn.reverse()); } } } |